Flip String to Monotone Increasing

How it works

We can solve this problem in a single pass by maintaining a running count of 1s seen so far and the minimum flips needed. When we see a 1, it might need to be flipped later if we decide that position should be 0. When we see a 0, we can either flip it to 1 (incrementing our flip count) or flip all previous 1s to 0.

The key insight is that the minimum flips at any position equals the minimum of: (1) flipping this 0 plus the previous minimum, or (2) flipping all 1s seen so far to 0s.

Steps

1. Initialize res (minimum flips) and cntOne (count of 1s seen) to 0.
2. Iterate through each character in the string.
3. If the character is '1', increment cntOne.
4. If the character is '0', update res = min(res + 1, cntOne):
   • res + 1 means flip this 0 to 1.
   • cntOne means flip all previous 1s to 0s instead.
5. Return res.

Complexity

• Time complexity: O(n)
• Space complexity: O(1) extra space.

Things to watch for

Misunderstanding the Monotone Increasing Property

A monotone increasing binary string means all 0s come before all 1s. Some incorrectly interpret this as strictly increasing values or allow alternating patterns. The valid forms are only: all zeros, all ones, or zeros followed by ones with exactly one transition point.

Forgetting to Track the Count of Ones

The optimal solution relies on tracking how many 1s have been seen so far. When encountering a 0, you must decide whether to flip it to 1 or flip all previous 1s to 0. Forgetting to maintain this count leads to incorrect flip calculations.

Off-by-One Errors in Split Point Logic

When using the prefix-suffix approach, the split point represents where zeros end and ones begin. The valid split points range from 0 (all ones) to n (all zeros). Missing the boundary cases or incorrectly indexing the prefix/suffix arrays causes wrong answers.

class Solution:
    def minFlipsMonoIncr(self, s: str) -> int:
        res  = cntOne = 0
        for c in s:
            if c == '1':
                cntOne += 1
            else:
                res = min(res + 1, cntOne)
        return res

class Solution {
public:
    int minFlipsMonoIncr(string s) {
        int res = 0, cntOne = 0;
        for (char& c : s) {
            if (c == '1') {
                cntOne++;
            } else {
                res = min(res + 1, cntOne);
            }
        }
        return res;
    }
};