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.
- 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 <= 100000s[i] is '0' or '1'.
Hints for Flip String to Monotone Increasing
Hint 1
Sweep left to right and keep two numbers: how many
1s you have seen, and the best cost so far.Hint 2
At a
0you either flip it to a1(costflips + 1) or flip every1before it to a0(costones).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
- Track
ones, the number of1s seen so far, andflips, the minimum cost for the prefix. - On a
1, incrementonesand leaveflipsalone — a trailing1is always free. - On a
0, setflips = 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 each0separately isO(n²). - Incrementing
flipson a1is wrong — a1never needs flipping if everything after it is a1. - Both parts of the result may be empty, so an all-
0or all-1string 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 flipsJava
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