LeetCode 926 - Flip String to Monotone Increasing

LeetCode Problem 926

Difficulty: 🟡 Medium
Topics: String, Dynamic Programming

Solution

Problem Understanding

The problem asks us to transform a binary string into a monotone increasing string using the minimum number of character flips.

A binary string is considered monotone increasing if all 0s appear before all 1s. In other words, once a 1 appears, no 0 can appear after it. Valid examples include:

• "000111"
• "111"
• "000"
• "" conceptually, though the constraints guarantee at least one character

Invalid examples include:

• "010"
• "101"
• "1100"

We are given a string s consisting only of '0' and '1'. We may flip any character:

• '0' → '1'
• '1' → '0'

Our goal is to compute the minimum number of flips required so that the final string becomes monotone increasing.

The constraints are important:

• 1 <= s.length <= 10^5
• The string contains only binary digits

A length of 10^5 means an exponential or quadratic solution would likely be too slow. We need an algorithm that runs in linear time, or close to it.

Several edge cases are important:

• Strings already monotone increasing, such as "000111" or "11111"
• Strings entirely composed of one character
• Alternating patterns like "010101"
• Cases where flipping earlier 1s is cheaper than flipping later 0s
• Very short strings such as "0" or "1"

A naive implementation can easily make incorrect greedy decisions if it only looks locally instead of considering the global structure of the string.

Approaches

Brute Force Approach

A monotone increasing binary string always has a boundary point:

• everything before the boundary is 0
• everything after the boundary is 1

For a string of length n, there are n + 1 possible boundaries.

For each boundary position i:

• characters before i should all be 0
• characters from i onward should all be 1

We can count:

• how many 1s appear before i, these must flip to 0
• how many 0s appear after i, these must flip to 1

The total flips for that boundary is:

(flips on left) + (flips on right)

We compute this for every possible boundary and take the minimum.

This works because every valid monotone increasing string can be represented by some split between 0s and 1s.

However, a naive implementation would scan the string for every boundary, producing O(n^2) time complexity, which is too slow for n = 10^5.

Key Insight for the Optimal Solution

The important observation is that while scanning the string from left to right, we only need two pieces of information:

• how many 1s we have seen so far
• the minimum flips needed so far

When we encounter a '0', we have two choices:

• flip this '0' to '1'
• flip all previous '1' characters to '0'

We choose the cheaper option.

This leads to a dynamic programming style solution with constant extra space.

At every step:

• ones_count tracks how many 1s have appeared
• flips tracks the minimum flips needed up to the current position

When we see:

• '1', we increment ones_count

• '0', we decide:

• flip current 0, cost becomes flips + 1

• flip previous 1s, cost becomes ones_count

So:

flips = min(flips + 1, ones_count)

This gives an elegant linear-time solution.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Try every split point and rescan the string
Optimal	O(n)	O(1)	Dynamic programming with running counts

Algorithm Walkthrough

1. Initialize two variables:

• ones_count = 0
• flips = 0

ones_count tracks how many 1s we have encountered so far. flips stores the minimum flips needed to make the processed prefix monotone increasing. 2. Iterate through the string character by character. 3. If the current character is '1':

• Increment ones_count

A 1 naturally fits into a monotone increasing sequence, so no immediate flip is needed. 4. If the current character is '0':

• This creates a potential violation because a 0 after earlier 1s breaks monotonicity.

• We have two possible fixes:

• Flip this 0 into 1

• cost becomes flips + 1

• Flip all previous 1s into 0

• cost becomes ones_count

5. Update:

flips = min(flips + 1, ones_count)

6. Continue until the entire string is processed.
7. Return flips.

Why it works

The algorithm maintains the invariant that after processing index i, flips equals the minimum flips needed to make the prefix s[0:i+1] monotone increasing.

Whenever we encounter a 0 after some 1s, there are only two valid possibilities:

• convert the current 0 into 1
• convert previous 1s into 0

The recurrence always chooses the cheaper option, guaranteeing an optimal result.

Python Solution

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

        for char in s:
            if char == '1':
                ones_count += 1
            else:
                flips = min(flips + 1, ones_count)

        return flips

The implementation closely follows the algorithm described earlier.

The variable ones_count records how many 1s have appeared so far. This matters because if we later encounter a problematic 0, one possible strategy is to flip all earlier 1s into 0s.

The variable flips stores the minimum flips required for the processed prefix.

When iterating through the string:

• A '1' simply increases ones_count

• A '0' forces a decision:

• flip this 0

• or flip previous 1s

The line:

flips = min(flips + 1, ones_count)

encodes this decision directly.

The algorithm only uses constant extra memory and processes each character exactly once.

Go Solution

func minFlipsMonoIncr(s string) int {
    onesCount := 0
    flips := 0

    for _, ch := range s {
        if ch == '1' {
            onesCount++
        } else {
            if flips+1 < onesCount {
                flips = flips + 1
            } else {
                flips = onesCount
            }
        }
    }

    return flips
}

The Go implementation is nearly identical to the Python version.

A few Go-specific details are worth noting:

• Strings in Go are iterated using range, which returns runes
• Integer overflow is not a concern because the maximum answer is at most 10^5
• No additional slices or arrays are needed, so memory usage remains constant
• Go does not have a built-in min function for integers, so the comparison is written explicitly

Worked Examples

Example 1

Input:

s = "00110"

Index	Character	ones_count	flips	Explanation
0	0	0	0	Already valid
1	0	0	0	Still valid
2	1	1	0	Count a 1
3	1	2	0	Count another 1
4	0	2	1	min(0 + 1, 2) = 1

Final answer:

1

We flip the last 0 into 1.

Example 2

Input:

s = "010110"

Index	Character	ones_count	flips	Explanation
0	0	0	0	Valid
1	1	1	0	Count 1
2	0	1	1	min(0 + 1, 1) = 1
3	1	2	1	Count 1
4	1	3	1	Count 1
5	0	3	2	min(1 + 1, 3) = 2

Final answer:

2

Example 3

Input:

s = "00011000"

Index	Character	ones_count	flips	Explanation
0	0	0	0	Valid
1	0	0	0	Valid
2	0	0	0	Valid
3	1	1	0	Count 1
4	1	2	0	Count 1
5	0	2	1	min(0 + 1, 2) = 1
6	0	2	2	min(1 + 1, 2) = 2
7	0	2	2	min(2 + 1, 2) = 2

Final answer:

2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is processed exactly once
Space	O(1)	Only two integer variables are used

The algorithm performs a single left-to-right scan of the string. No nested loops or auxiliary data structures are required.

Because only constant-sized variables are maintained regardless of input size, the extra space complexity is constant.

Test Cases

solution = Solution()

assert solution.minFlipsMonoIncr("00110") == 1  # Provided example
assert solution.minFlipsMonoIncr("010110") == 2  # Provided example
assert solution.minFlipsMonoIncr("00011000") == 2  # Provided example

assert solution.minFlipsMonoIncr("0") == 0  # Single zero
assert solution.minFlipsMonoIncr("1") == 0  # Single one

assert solution.minFlipsMonoIncr("00000") == 0  # Already monotone
assert solution.minFlipsMonoIncr("11111") == 0  # Already monotone

assert solution.minFlipsMonoIncr("10") == 1  # One flip needed
assert solution.minFlipsMonoIncr("01") == 0  # Already valid

assert solution.minFlipsMonoIncr("101010") == 3  # Alternating pattern
assert solution.minFlipsMonoIncr("11011") == 1  # Flip middle zero
assert solution.minFlipsMonoIncr("000111") == 0  # Perfect monotone
assert solution.minFlipsMonoIncr("111000") == 3  # Multiple flips needed

assert solution.minFlipsMonoIncr("10011111110010111011") == 5  # Larger mixed case

Test	Why
"00110"	Standard example with one flip
"010110"	Multiple optimal solutions
"00011000"	Best solution flips trailing zeros
"0"	Minimum length input
"1"	Minimum length with one
"00000"	All zeros
"11111"	All ones
"10"	Small invalid string
"01"	Small valid string
"101010"	Alternating pattern stress test
"11011"	Internal zero must flip
"000111"	Already monotone increasing
"111000"	Requires several flips
"10011111110010111011"	Larger mixed input

Edge Cases

Strings Already Monotone Increasing

Inputs like "000111" or "11111" are already valid. A buggy implementation might perform unnecessary flips because it does not properly recognize valid prefixes.

This implementation handles these correctly because:

• encountering 1s only increments ones_count
• encountering leading 0s does not increase flips

As a result, flips remains 0.

All Characters the Same

Strings containing only 0s or only 1s are trivially monotone increasing.

Examples:

• "00000"
• "11111"

Some implementations incorrectly assume both digits must appear. This solution does not make that assumption and naturally returns 0.

Alternating Patterns

Inputs like "101010" are challenging because local greedy choices can fail.

For example:

101010

At several points, the algorithm must decide whether it is cheaper to flip:

• the current 0
• or previous 1s

The recurrence:

min(flips + 1, ones_count)

ensures the globally optimal choice is preserved at every step.

Very Short Strings

Strings of length 1 can easily expose off-by-one errors.

Examples:

• "0"
• "1"

Since the loop processes characters independently and no indexing tricks are used, the implementation handles these safely without special-case logic.