Flip String to Monotone Increasing
MedPrompt
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'.
Approaches
3 approaches with complexity analysis and trade-offs.
A monotone increasing binary string has a structure of some number of 0s followed by some number of 1s. This implies there's a "split point" where the 0s end and the 1s begin. A brute-force approach is to try every possible split point, calculate the number of flips needed for that specific split, and then find the minimum among all possibilities.
Algorithm
- Initialize
min_flipsto a very large number. - Get the length of the string,
n. - Loop
ifrom0ton. Thisirepresents the split point where0s end and1s begin. - Inside the loop, initialize
current_flips = 0. - Calculate flips for the prefix
s[0...i-1]to become all0s. This is done by iterating fromj = 0toi-1and counting the number of'1's. - Calculate flips for the suffix
s[i...n-1]to become all1s. This is done by iterating fromj = iton-1and counting the number of'0's. - Update
min_flips = min(min_flips, current_flips). - After the outer loop finishes,
min_flipswill hold the minimum number of flips required.
Walkthrough
The algorithm iterates through every possible index i from 0 to n (where n is the string length) as the potential split point. For each i, the string is conceptually divided into a prefix s[0...i-1] and a suffix s[i...n-1]. To make the string monotone increasing with this split, the prefix must consist entirely of 0s, and the suffix must consist entirely of 1s. The cost (number of flips) for this split is the count of 1s in the prefix plus the count of 0s in the suffix. We calculate this cost for every possible i and maintain the minimum cost found. The edge cases i=0 (target string is all 1s) and i=n (target string is all 0s) are naturally handled by the loops.
class Solution { public int minFlipsMonoIncr(String s) { int n = s.length(); int minFlips = Integer.MAX_VALUE; // Iterate through all possible split points for (int i = 0; i <= n; i++) { int currentFlips = 0; // Flips for prefix s[0...i-1] to be all '0's for (int j = 0; j < i; j++) { if (s.charAt(j) == '1') { currentFlips++; } } // Flips for suffix s[i...n-1] to be all '1's for (int j = i; j < n; j++) { if (s.charAt(j) == '0') { currentFlips++; } } minFlips = Math.min(minFlips, currentFlips); } return minFlips; }}Complexity
Time
O(n^2) - The outer loop runs `n+1` times. For each iteration, the inner loops scan the entire string to count flips, taking O(n) time. This results in a quadratic time complexity.
Space
O(1) - We only use a few variables to store counts and the minimum value, regardless of the input string size.
Trade-offs
Pros
Simple to understand and implement.
Correctly solves the problem for small inputs.
Cons
Highly inefficient due to nested loops.
Will result in a 'Time Limit Exceeded' error on platforms like LeetCode for the given constraints.
Solutions
Solution
class Solution { public int minFlipsMonoIncr ( String s ) { int n = s . length (); int [] left = new int [ n + 1 ]; int [] right = new int [ n + 1 ]; int ans = Integer . MAX_VALUE ; for ( int i = 1 ; i <= n ; i ++) { left [ i ] = left [ i - 1 ] + ( s . charAt ( i - 1 ) == '1' ? 1 : 0 ); } for ( int i = n - 1 ; i >= 0 ; i --) { right [ i ] = right [ i + 1 ] + ( s . charAt ( i ) == '0' ? 1 : 0 ); } for ( int i = 0 ; i <= n ; i ++) { ans = Math . min ( ans , left [ i ] + right [ i ]); } return ans ; } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.