Flip String to Monotone Increasing

Medium
731.

Flip String to Monotone Increasing

Flip String to Monotone Increasing is a medium coding problem on strings, dynamic programming and bit manipulation, asked in Amazon, Google and Meta interviews.

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'.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var minFlipsMonoIncr = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Flip String to Monotone Increasing — Problem & Solution

Flip String to Monotone Increasing solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Flip String to Monotone Increasing is a medium coding problem on strings, dynamic programming and bit manipulation, asked in Amazon, Google and Meta interviews.

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'.

Hints for Flip String to Monotone Increasing

  1. Hint 1

    Sweep left to right and keep two numbers: how many 1s you have seen, and the best cost so far.

  2. Hint 2

    At a 0 you either flip it to a 1 (cost flips + 1) or flip every 1 before it to a 0 (cost ones).

  3. Hint 3

    Take the smaller of those two.

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

  1. Track ones, the number of 1s seen so far, and flips, the minimum cost for the prefix.
  2. On a 1, increment ones and leave flips alone — a trailing 1 is always free.
  3. On a 0, set flips = min(flips + 1, ones).
  4. 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

Java

public static int minFlipsMonoIncr(String s) {
    int ones = 0, flips = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '1') ones++;
        else flips = Math.min(flips + 1, ones);
    }
    return flips;
}

C++

int minFlipsMonoIncr(string s) {
    int ones = 0, flips = 0;
    for (char c : s) {
        if (c == '1') ones++;
        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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Dynamic Programming