Flip String to Monotone Increasing

Similar Problems:

- LintCode: Computer Maintenance
- CheatSheet: Leetcode For Code Interview
- Tag: #dynamicprogramming, #inspiring

A string of ‘0’s and ‘1’s is monotone increasing if it consists of some number of ‘0’s (possibly 0), followed by some number of ‘1’s (also possibly 0.)

We are given a string S of ‘0’s and ‘1’s, and we may flip any ‘0’ to a ‘1’ or a ‘1’ to a ‘0’.

Return the minimum number of flips to make S monotone increasing.

Example 1:

Input: "00110" Output: 1 Explanation: We flip the last digit to get 00111.

Example 2:

Input: "010110" Output: 2 Explanation: We flip to get 011111, or alternatively 000111.

Example 3:

Input: "00011000" Output: 2 Explanation: We flip to get 00000000.

Note:

- 1 <= S.length <= 20000
- S only consists of ‘0’ and ‘1’ characters.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

- Solution:

// https://code.dennyzhang.com/flip-string-to-monotone-increasing // Basic Ideas: dynamic programming // dp[i][0]: how many changes to the make the sequence ends with 0 // dp[i][1]: how many changes to the make the sequence ends with 1 // Complexity: Time O(n), Space O(n) func minFlipsMonoIncr(S string) int { len_s := len(S) dp := make([][]int, len_s) for i := range dp { dp[i] = []int{0, 0} } for i, ch := range S { if i == 0 { if ch == '1' { dp[i][0] = 1 } if ch == '0' { dp[i][1] = 1 } continue } min := dp[i-1][0] if dp[i-1][1] < min { min = dp[i-1][1] } if ch == '0' { dp[i][0] = dp[i-1][0] dp[i][1] = min + 1 } else { dp[i][0] = dp[i-1][0] + 1 dp[i][1] = min } } res := dp[len_s-1][1] if dp[len_s-1][0] < dp[len_s-1][1] { res = dp[len_s-1][0] } return res }