926. Flip String to Monotone Increasing

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. 1 <= S.length <= 20000
2. S only consists of '0' and '1' characters.

 

Approach #1: DP + Prefix + Suffix. [Java]

class Solution {
    public int minFlipsMonoIncr(String S) {
        int n = S.length();
        int[] l = new int[n+1];
        int[] r = new int[n+1];
        l[0] = S.charAt(0) - '0';
        r[n-1] = '1' - S.charAt(n-1);
        for (int i = 1; i < n; ++i) 
            l[i] = l[i-1] + S.charAt(i) - '0';
        for (int j = n-2; j >= 0; --j)
            r[j] = r[j+1] + '1' - S.charAt(j);
        int ret = r[0];
        for (int i = 1; i <= n; ++i)
            ret = Math.min(ret, l[i-1] + r[i]);
        return ret;
    }
}

 

Analysis:

l[i] = of min flips -> S[0] ~ S[i] all 0s.

r[i] = of min flips -> S[i] ~ S[n-1] all 1s.

ans = min{l[i-1] + r[i], l[n-1], r[0]}

l[i] = l[i-1] + s[i] == '1'

r[i] = r[i+1] + s[i] == '0'

Time complexity: O(n)

Space complexity: O(n)

 

　　

Approach #2: DP. [C++]

class Solution {
public:
    int minFlipsMonoIncr(string S) {
        int n = S.length();
        vector<vector<int>> dp(n+1, vector<int>(2, 0));
        for (int i = 1; i <= n; ++i) {
            if (S[i-1] == '0') {
                dp[i][0] = dp[i-1][0];
                dp[i][1] = min(dp[i-1][0], dp[i-1][1]) + 1;
            } else {
                dp[i][0] = dp[i-1][0] + 1;
                dp[i][1] = min(dp[i-1][0], dp[i-1][1]);
            }
        }
        return min(dp[n][0], dp[n][1]);
    }
};

　　

Analysis:

dp[i][0] = ans of S[0, i-1] and S[i] == '0'.

d[i][1] = ans of S[0, i-1] and S[i] == '1'.

if S[i] == '0':

　　dp[i][0] = dp[i-1][0];

　　dp[i][1] = min(dp[i-1][0], dp[i-1][1]) + 1;

else:

　　dp[i][0] = dp[i-1][0];

　　dp[i][1] = min(dp[i-1][0], dp[i-1][1])

 

Reference:

https://zxi.mytechroad.com/blog/dynamic-programming/leetcode-926-flip-string-to-monotone-increasing/