A binary string is monotone increasing if it consists of some number of 0's (possibly none), followed by some number of 1's (also possibly none).
You are given a binary string s. You can flip s[i] changing it from 0 to 1 or from 1 to 0.
Return the minimum number of flips to make s monotone increasing.
Example 1:
Input: s = "00110" Output: 1 Explanation: We flip the last digit to get 00111.
Example 2:
Input: s = "010110" Output: 2 Explanation: We flip to get 011111, or alternatively 000111.
Example 3:
Input: s = "00011000" Output: 2 Explanation: We flip to get 00000000.
Constraints:
1 <= s.length <= 105s[i] is either '0' or '1'.Problem Overview: You are given a binary string s. The goal is to flip the minimum number of characters so the string becomes monotone increasing—all 0s appear before any 1s. Any character can be flipped (0 → 1 or 1 → 0), and you must return the minimum number of flips required.
Approach 1: Prefix Sum Method (O(n) time, O(n) space)
This approach tries every possible split point where the string transitions from 0s to 1s. For each index i, the left side should contain only 0s and the right side only 1s. Use prefix sums to count how many 1s appear on the left (these must flip to 0) and how many 0s appear on the right (these must flip to 1). Iterate through all split points and compute leftOnes + rightZeros. The minimum across all splits gives the answer. This technique is a classic application of string processing combined with prefix sum counting.
Approach 2: Dynamic Programming (O(n) time, O(1) space)
Track two running values while scanning the string once. Let ones count how many 1s have appeared so far, and flips represent the minimum flips required up to the current position. When you see a 1, simply increment ones because it fits the monotone pattern. When you see a 0, you have two choices: flip this 0 to 1 (cost flips + 1) or flip all previous 1s to 0 (cost ones). Update flips = min(flips + 1, ones). This greedy-style DP keeps the optimal answer for each prefix and avoids storing extra arrays. The technique is common in dynamic programming problems where decisions depend on previous states.
Recommended for interviews: The Dynamic Programming approach is usually what interviewers expect. It processes the string in one pass, uses constant space, and shows you can convert a global constraint into incremental decisions. The prefix sum approach is still valuable because it demonstrates clear reasoning about split points and counting, but the DP solution shows stronger optimization skills.
This approach utilizes prefix sums to calculate the minimum number of flips required to make a binary string monotone increasing. The idea is to traverse the string while maintaining a prefix count of '1's and suffix count of '0's. For each position i, calculate how many flips would be necessary to make all characters before i '0' + make all characters from i '1'.
This solution iterates through the string and calculates prefix sums for '1's. Then it computes the potential flips required at each breakpoint to make the string monotone increasing and returns the minimum.
Python
C++
Java
C#
JavaScript
Time Complexity: O(n) where n is the length of the string.
Space Complexity: O(n) due to the prefix ones array.
This approach leverages dynamic programming to find the minimum flips. Two states are maintained for any position: one representing the minimal flips to have a monotone ending with '0' and the other with '1'. Update these states as we traverse the string.
The dynamic programming approach maintains two counters that track the minimal flips for maintaining monotonic sequences. As the string is parsed, appropriate states are updated.
Python
C++
Java
C#
JavaScript
Time Complexity: O(n) as we traverse across the string once.
Space Complexity: O(1) since only fixed states are maintained.
First, we count the number of '0's in string s, denoted as tot. We define a variable ans for the answer, initially set ans = tot, which represents the number of flips to change all '0's to '1's.
Then, we can enumerate each position i, change all '1's to the left of position i (including i) to '0', and change all '0's to the right of position i to '1'. We calculate the number of flips in this case, which is i + 1 - cur + tot - cur, where cur represents the number of '0's to the left of position i (including i). We update the answer ans = min(ans, i + 1 - cur + tot - cur).
Finally, return the answer ans.
The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| Prefix Sum Method | Time Complexity: O(n) where n is the length of the string. |
| Dynamic Programming | Time Complexity: O(n) as we traverse across the string once. |
| Prefix Sum + Enumeration | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Prefix Sum Method | O(n) | O(n) | When reasoning about split points or teaching the intuition behind counting flips on both sides |
| Dynamic Programming | O(n) | O(1) | Best for interviews and production code due to single pass and constant memory |
Flip String to Monotone Increasing - Leetcode 926 - Python • NeetCodeIO • 15,688 views views
Watch 9 more video solutions →Practice Flip String to Monotone Increasing with our built-in code editor and test cases.
Practice on FleetCode