Formatted question description: https://leetcode.ca/all/926.html

926. Flip String to Monotone Increasing (Medium)

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.

Solution 1. Two Pass

When we separate the string into two parts, the flip count is the sum of:

  • The ones at the left side
  • The zeros at the right side.

So we try different separation points from left to right, and for each trial we can easily get the flip count by keeping track of the above two counts.

// OJ: https://leetcode.com/problems/flip-string-to-monotone-increasing/

// Time: O(N)
// Space: O(1)
class Solution {
public:
    int minFlipsMonoIncr(string S) {
        int rightZeros = 0, leftOnes = 0;
        for (char c : S) if (c == '0') rightZeros++;
        int ans = rightZeros;
        for (char c : S) {
            if (c == '1') leftOnes++;
            else rightZeros--;
            ans = min(ans, rightZeros + leftOnes);
        }
        return ans;
    }
};

Solution 2. One Pass

Think in the DP way. Assume we’ve already solved the sub-problem for substring S[0..i], and the solution for it is flipCount[i].

Then we look at the next character S[i + 1].

  • If it’s 1, we can simply use the solution for S[0..i], so flipCount[i + 1] = flipCount[i].
  • If it’s 0, think about the options we have:
    1. Firstly, we can choose to flip this 0 to 1 and reuse the solution for S[0..i]. In this case flipCount[i + 1] = flipCount[i] + 1.
    2. What if the best solution is not to flip? Then we need to turn all 1s in S[0..i] into 0. Assume the count of 1s in S[0..i] is ones[i], then flipCount[i + 1] = ones[i]

    Given these two options, we pick the one with smaller result.

In sum:

flipCount[0] = 0
ones[0] = 0

flipCount[i + 1] = flipCount[i]                   (if S[i + 1] == '1')
                   min(flipCount[i] + 1, ones[i]) (if S[i + 1] == '0')
    where 1 <= i <= N - 2
// OJ: https://leetcode.com/problems/flip-string-to-monotone-increasing/

// Time: O(N)
// Space: O(1)
// Ref: https://leetcode.com/problems/flip-string-to-monotone-increasing/discuss/189751/C%2B%2B-one-pass-DP-solution-0ms-O(n)-or-O(1)-one-line-with-explaination.
class Solution {
public:
    int minFlipsMonoIncr(string S) {
        int ones = 0, ans = 0;
        for (char c : S) {
            if (c == '1') ones++;
            else ans = min(ans + 1, ones);
        }
        return ans;
    }
};

Java

class Solution {
    public int minFlipsMonoIncr(String S) {
        if (S == null || S.length() <= 1)
            return 0;
        int length = S.length();
        int[][] dp = new int[length][2];
        if (S.charAt(0) == '0')
            dp[0][1] = 1;
        else
            dp[0][0] = 1;
        for (int i = 1; i < length; i++) {
            dp[i][0] = dp[i - 1][0];
            dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][1]);
            char c = S.charAt(i);
            if (c == '0')
                dp[i][1]++;
            else
                dp[i][0]++;
        }
        return Math.min(dp[length - 1][0], dp[length - 1][1]);
    }
}

All Problems

All Solutions