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/