Flip String to Monotone Increasing — Medium Problem & Solution

A binary string is monotone increasing when it consists of some number of 0s followed by some number of 1s — either part may be empty.

Difficulty: Medium
Topics: Strings, Dynamic Programming, Bit Manipulation
Asked at: Amazon, Google, Meta
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A binary string is monotone increasing when it consists of some number of 0s followed by some number of 1s — either part may be empty.

One flip changes a 0 to a 1 or a 1 to a 0. Return the minimum number of flips that makes s monotone increasing.

Example 1

Input: s = "00110"
Output: 1
Explanation: Flipping the last 0 to a 1 gives "00111".

Example 2

Input: s = "010110"
Output: 2
Explanation: "011111" or "000111" both take two flips.

Example 3

Input: s = "00011000"
Output: 2
Explanation: Flipping the two 1s gives "00000000".

Constraints

1 <= s.length <= 100000
s[i] is '0' or '1'.

How to solve Flip String to Monotone Increasing

Scan once. At each 0, the prefix must end either in 1s — meaning this 0 gets flipped — or in 0s, meaning all earlier 1s get flipped. Keeping both running quantities makes the decision local.

Approach

Track ones, the number of 1s seen so far, and flips, the minimum cost for the prefix.
On a 1, increment ones and leave flips alone — a trailing 1 is always free.
On a 0, set flips = min(flips + 1, ones).
Return flips.

Why it works

flips + 1 is the cost of keeping the prefix's shape and flipping this 0 up; ones is the cost of making the whole prefix 0s. Every monotone target is one of these two shapes at each position, so the minimum of the two is the optimum for that prefix.

Complexity

Time — O(n)
Space — O(1)

Pitfalls

Counting the 1s before each 0 separately is O(n²).
Incrementing flips on a 1 is wrong — a 1 never needs flipping if everything after it is a 1.
Both parts of the result may be empty, so an all-0 or all-1 string costs nothing.

Reference solution

Python

def minFlipsMonoIncr(s: str) -> int:
    ones = flips = 0
    for c in s:
        if c == "1":
            ones += 1
        else:
            flips = min(flips + 1, ones)
    return flips

JavaScript

var minFlipsMonoIncr = function(s) {
    var ones = 0, flips = 0;
    for (var i = 0; i < s.length; i++) {
        if (s.charAt(i) === "1") ones++;
        else flips = Math.min(flips + 1, ones);
    }
    return flips;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue