The original article is available at https://dawnmagnet.top/leetcode/2022/06/11/.

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

Given a binary string s, you may flip any 0 to 1 or any 1 to 0.

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

Example 1:

**Input:** s = "00110"
**Output:** 1
**Explanation:** Flip the last character to obtain 00111.

Example 2:

**Input:** s = "010110"
**Output:** 2
**Explanation:** Flip characters to obtain 011111 or 000111.

Example 3:

**Input:** s = "00011000"
**Output:** 2
**Explanation:** Flip characters to obtain 00000000.

Constraints:

1 <= s.length <= 105 s[i] is either ‘0’ or ‘1’. Source: LeetCode Link: https://leetcode.cn/problems/flip-string-to-monotone-increasing Copyright belongs to LeetCode. For commercial use, contact the official copyright holder; for non-commercial use, cite the source as required.

Analysis - 1

#

The key difficulty is minimizing the number of flips. Choose one exact position in the string as the boundary between 0 and 1. Once the boundary is fixed, turn every 1 before it into 0 and every 0 after it into 1; the total number of flips can then be calculated directly.

The remaining question is how to quickly count the 1s before a given boundary and the 0s after it. A dynamic-programming approach is natural: use two arrays and traverse the string from both directions to obtain these counts for every position. Then make one more pass, add the two counts for each possible boundary, and take the minimum cost.

C++ Code - 1

#

class Solution {
public:
    int minFlipsMonoIncr(string s) {
        int n = s.size();
        vector<int> v1(n + 1), v2(n + 1);
        for (int i = 0; i < n; ++i) v1[i + 1] = v1[i] + (s[i] == '1');
        for (int i = n - 1; i >= 0; --i) v2[i] = v2[i + 1] + (s[i] == '0');
        int res = n;
        for (int i = 0; i <= n; ++i)
            res = min(res, v1[i] + v2[i]);
        return res;
    }
};

Analysis 2

#

The previous approach can be optimized because it uses two full arrays. We can solve the problem in O(1) extra space with another dynamic-programming formulation.

Suppose a string has minimum flip count n. If we append one character, can we compute the minimum flip count for the new string?

If the appended character is 1, either 0 or 1 may precede it, so no additional flip is needed.

If the appended character is 0, it must be preceded by 0, so again no additional flip is needed for that valid state.

Because the last character of the previous string affects the possible state after each flip, we must consider the two ending characters separately.

Let dp[i][j] be a dynamic-programming array whose value is the minimum number of flips for the substring s[0:i] when its final character after flipping is j (where j is 0 or 1).

The following transitions handle the case where the appended character is not flipped:

• If the appended character is 0, then dp[i][0]=dp[i-1][0].
• If the appended character is 1, then dp[i][1]=min(dp[i-1][0], dp[i-1][1]).

If the appended character itself must be flipped, add one flip:

• If the appended character is 0, then dp[i][1]=min(dp[i-1][0], dp[i-1][1])+1.
• If the appended character is 1, then dp[i][0]=dp[i-1][0]+1.

Together, these form a consistent dynamic-programming recurrence.

C++ Code - 2

#

class Solution {
public:
    int minFlipsMonoIncr(string s) {
        int a = 0, b = 0;
        for (auto & ch : s) {
            b = min(a, b);
            if (ch == '1') a++;
            else b++;
        }
        return min(a, b);
    }
};