926

926. Flip String to Monotone Increasing (Medium)

A binary string is monotone increasing if it consists of some number of 0's (possibly none), followed by some number of 1's (also possibly none).

You are given a binary string s. You can flip s[i] changing it from 0 to 1 or from 1 to 0.

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

 

Example 1:

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

Example 2:

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

Example 3:

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

 

Constraints:

• 1 <= s.length <= 105
• s[i] is either '0' or '1'.

Companies:
Amazon

Related Topics:
String, Dynamic Programming

Solution 1. Two Passes

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/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int minFlipsMonoIncr(string s) {
        int rightZeros = 0, leftOnes = 0;
        for (char c : s) rightZeros += c == '0';
        int ans = rightZeros;
        for (char c : s) { // we make the current character the last `0`
            if (c == '1') leftOnes++;
            else rightZeros--;
            ans = min(ans, rightZeros + leftOnes);
        }
        return ans;
    }
};

Solution 2. One Pass (DP)

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, we can pick the best one from these two options:
  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]

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/
// Author: github.com/lzl124631x
// 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;
    }
};