Flip String to Monotone Increasing: Prefix Counting

May 24, 20266 min read

leetcodeproblemmediumstringsdynamic-programming

You are given a binary string s consisting only of '0' and '1'. You can flip any character (change '0' to '1' or '1' to '0'). Return the minimum number of flips to make s monotone increasing, meaning all the '0's come before all the '1's.

This is LeetCode 926: Flip String to Monotone Increasing, a medium problem that teaches you how to use prefix counting and a running DP state to solve problems in a single pass. The key insight is that you never need to try every possible split point explicitly. You can track just two numbers as you scan left to right.

s = "00110". Flip the last '0' to '1' for a cost of 1. The result "00111" is monotone increasing.

Why this problem matters

Flip String to Monotone Increasing is a clean example of reducing a seemingly complex decision (which characters to flip) to a simple running calculation. At every position, you face a choice: flip this '0' to '1', or retroactively flip all the '1's you have seen so far to '0'. The minimum of those two costs gives you the answer at each step.

This "running minimum" pattern shows up in many DP and prefix-sum problems. Once you see how to reduce a multi-dimensional decision space to a single-pass O(1)-state computation, you can apply the same trick to problems like Best Time to Buy and Sell Stock, Maximum Subarray, and others that look harder than they are.

The split point intuition

One way to think about this problem: imagine placing a vertical divider somewhere in the string. Everything to the left of the divider should be '0', and everything to the right should be '1'. The cost of a particular split point is:

Number of '1's to the left of the divider (they need to become '0')
Plus the number of '0's to the right of the divider (they need to become '1')

You want the split point that minimizes this total cost. You could compute prefix sums and try all n + 1 split positions, but there is an even simpler way.

The key insight: tracking ones and flips

Instead of explicitly trying all split points, you can scan left to right and maintain two variables:

ones: how many '1's you have seen so far
flips: the minimum flips needed to make the string monotone up to the current position

For each character:

If it is '1', increment ones. A '1' at the end never hurts monotonicity, so flips stays the same.
If it is '0', you have two choices: flip this '0' to '1' (cost: flips + 1), or flip all previous '1's to '0' (cost: ones). Take the minimum.

This is essentially a DP where the state is just flips, updated in O(1) at each step.

Think of flips as the best answer so far if the string ended at the current position. Each new character either leaves it unchanged (for '1') or forces a decision (for '0').

The solution

def minFlipsMonoIncr(s):
    ones = 0
    flips = 0
    for c in s:
        if c == '1':
            ones += 1
        else:
            flips = min(flips + 1, ones)
    return flips

Two variables, one loop. Here is what each piece does:

ones counts how many '1's you have encountered so far. This represents the cost of "reset everything to all zeros up to here."
flips is the running minimum cost to make the string monotone up to the current index.
When you see a '1', it extends the monotone suffix naturally. No additional flips needed.
When you see a '0', either flip it to '1' (adding 1 to the current flips count) or declare that the split point is here and flip all previous '1's (cost is ones). You take whichever is cheaper.
After processing the entire string, flips holds the answer.

Walking through it step by step

Let's trace through s = "00110" to see how ones and flips evolve at each position.

Step 1: i=0, s[0]='0'

s[0] is '0'. flips = min(flips + 1, ones) = min(0 + 1, 0) = 0. No flip needed yet.

Step 2: i=1, s[1]='0'

s[1] is '0'. flips = min(0 + 1, 0) = 0. Still no ones seen, so flipping all ones (zero of them) is free.

Step 3: i=2, s[2]='1'

s[2] is '1'. ones increments to 1. flips stays at 0. A '1' never increases the flip count.

Step 4: i=3, s[3]='1'

s[3] is '1'. ones increments to 2. flips stays at 0. Two ones seen, still zero flips needed.

Step 5: i=4, s[4]='0'

s[4] is '0'. flips = min(0 + 1, 2) = 1. Cheaper to flip this one '0' to '1' than to flip both previous ones.

Step 6: Done. Return flips = 1

Scan complete. The minimum number of flips to make "00110" monotone increasing is 1.

The final answer is 1. We flip the last '0' to '1', giving us "00111" which is monotone increasing.

Practice this problem with spaced repetition

Complexity analysis

Metric	Value
Time	O(n), single pass through the string
Space	O(1), only two integer variables

This is optimal. You must look at every character at least once to determine which flips are needed, so O(n) is the lower bound. And O(1) space means no auxiliary arrays or data structures.

Building blocks

This problem is built on two reusable patterns that CodeBricks drills independently.

1. Prefix counting

The pattern of maintaining a running count as you scan through a sequence:

count = 0
for item in sequence:
    if condition(item):
        count += 1
    use_count_to_make_decision()

In Flip String to Monotone Increasing, the prefix count is ones (how many '1's seen so far). In problems like Count of Smaller Numbers After Self, prefix counts track how many elements satisfy a property. The idea is the same: accumulate information left-to-right and use it to make O(1) decisions.

2. DP with running state

The pattern of maintaining a DP value that updates in constant time at each step:

dp = 0
for item in sequence:
    dp = transition(dp, item, auxiliary_info)
return dp

In this problem, flips is the DP state and the transition is min(flips + 1, ones) for zeros. In Maximum Subarray (Kadane's algorithm), the DP state is the current maximum sum. In Best Time to Buy and Sell Stock, the DP state is the minimum price seen. These all share the same skeleton: one pass, O(1) state, O(1) transition.

When a problem asks "minimum cost to transform a sequence into one satisfying a property," look for a way to express the choice at each position as a function of a small running state. If you can, you get a single-pass O(1)-space solution.

Edge cases

Before submitting, make sure your solution handles these:

Already monotone "000111": no flips needed. flips stays at 0 throughout. Returns 0.
All zeros "00000": already monotone increasing. Returns 0.
All ones "11111": already monotone increasing. Returns 0.
Alternating "010101": each '0' after a '1' forces a decision. The algorithm picks the cheapest combination of flips.
Single character "0" or "1": trivially monotone. Returns 0.
Worst case "1111...0000" (all ones followed by all zeros): the answer is min(count_of_ones, count_of_zeros). The running state naturally converges to this.

The single-pass solution handles all of these without special-case logic.

Build your pattern library with CodeBricks

From understanding to recall

You have read the solution and the logic is clear. Two variables, one comparison per character, done. But can you write it from scratch in an interview without hesitation?

The subtlety is in the transition: flips = min(flips + 1, ones) only applies to '0' characters, while '1' characters only increment ones. Getting this backwards or applying the wrong update to the wrong character is an easy mistake under pressure.

Spaced repetition closes that gap. You write the single-pass DP loop from scratch at increasing intervals. After a few rounds, you see "make binary string monotone" and your hands write the two-variable scan without conscious effort.

The prefix counting and running-state DP patterns are two of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Candy - Another problem where you scan in one direction tracking a running state to minimize cost
Non-decreasing Array - Deciding which elements to modify to achieve a monotone property
Partition Labels - Single-pass greedy with prefix information to find optimal boundaries

CodeBricks breaks the flip string to monotone increasing LeetCode problem into its prefix counting and running-state DP building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a monotone transformation question shows up in your interview, you do not think about it. You just write it.

Try CodeBricks free