LeetCode 926: Flip String to Monotone Increasing

Problem Restatement

We are given a binary string s.

Each character is either '0' or '1'.

A binary string is monotone increasing when all 0s come before all 1s. It may contain only 0s, only 1s, or both.

Valid examples:

"000"
"111"
"000111"
"001111"

Invalid examples:

"10"
"101"
"010"

We may flip any character:

0 -> 1
1 -> 0

Return the minimum number of flips needed to make s monotone increasing. The official statement gives examples such as "00110" -> 1, "010110" -> 2, and "00011000" -> 2.

Input and Output

Function shape:

class Solution:
    def minFlipsMonoIncr(self, s: str) -> int:
        ...

Examples

Example 1:

s = "00110"

The string is almost monotone increasing.

We can flip the last character:

00110 -> 00111

That takes 1 flip.

So the answer is:

1

Example 2:

s = "010110"

One valid result is:

010110 -> 011111

Another valid result is:

010110 -> 000111

Both take 2 flips.

So the answer is:

2

Example 3:

s = "00011000"

We can flip the two 1s into 0s:

00011000 -> 00000000

That takes 2 flips.

So the answer is:

2

First Thought: Try Every Split

A monotone increasing binary string has one split point:

000...000111...111

Everything before the split should be 0.

Everything after the split should be 1.

So one direct solution is to try every possible split.

For each split:

1. Count how many 1s appear on the left.
2. Count how many 0s appear on the right.
3. Flip those characters.

For example:

s = "010110"

If we choose the split after the third character:

010 | 110

The left side should be all 0s, so the 1 on the left must be flipped.

The right side should be all 1s, so the 0 on the right must be flipped.

Total flips:

1 + 1 = 2

This idea works, but scanning both sides for every split would be too slow.

Key Insight

We can process the string from left to right and keep only two values:

When we see a 1, it already fits the increasing order. We can keep it and increment ones.

When we see a 0, there is a conflict if previous 1s exist.

For this 0, we have two choices:

1. Flip this 0 to 1.
2. Keep this 0, but flip all previous 1s to 0.

So the recurrence is:

flips = min(flips + 1, ones)

Meaning:

Algorithm

Initialize:

ones = 0
flips = 0

Then scan each character c in s.

If c == '1':

ones += 1

If c == '0':

flips = min(flips + 1, ones)

Finally return:

flips

Walkthrough

Use:

s = "010110"

Start:

ones = 0
flips = 0

The answer is:

2

Correctness

At every position, flips stores the minimum number of flips needed to make the prefix ending at that position monotone increasing.

When the current character is 1, appending it to a monotone increasing prefix keeps the prefix valid, because 1 may appear after 0s or after other 1s. So flips does not change.

When the current character is 0, appending it after previous 1s may break monotone order. There are exactly two valid ways to repair this:

1. Flip the current 0 into 1, which costs flips + 1.
2. Keep the current 0, which means every previous 1 must become 0, costing ones.

The algorithm takes the smaller of these two choices.

These two choices cover all valid monotone forms for the current prefix. Therefore, after each character, flips remains the minimum possible cost for that prefix.

After the final character, the prefix is the whole string, so flips is the minimum number of flips needed for the whole string.

Complexity

Implementation

class Solution:
    def minFlipsMonoIncr(self, s: str) -> int:
        ones = 0
        flips = 0

        for c in s:
            if c == "1":
                ones += 1
            else:
                flips = min(flips + 1, ones)

        return flips

Code Explanation

ones counts how many 1s we have seen so far.

ones = 0

flips stores the best answer for the prefix processed so far.

flips = 0

When we see a 1, it can stay where it is.

if c == "1":
    ones += 1

When we see a 0, it may violate the monotone increasing order if earlier 1s exist.

flips = min(flips + 1, ones)

flips + 1 means we flip the current 0 into 1.

ones means we keep the current 0, but flip all previous 1s into 0.

The smaller value gives the best result for the current prefix.

Testing

def run_tests():
    s = Solution()

    assert s.minFlipsMonoIncr("00110") == 1
    assert s.minFlipsMonoIncr("010110") == 2
    assert s.minFlipsMonoIncr("00011000") == 2
    assert s.minFlipsMonoIncr("0") == 0
    assert s.minFlipsMonoIncr("1") == 0
    assert s.minFlipsMonoIncr("00000") == 0
    assert s.minFlipsMonoIncr("11111") == 0
    assert s.minFlipsMonoIncr("111000") == 3
    assert s.minFlipsMonoIncr("101010") == 3

    print("all tests passed")

run_tests()