Problem

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.

Examples

Example 1:

1
2
3

Input: s = "00110"
Output: 1
Explanation: We flip the last digit to get 00111.

Example 2:

1
2
3

Input: s = "010110"
Output: 2
Explanation: We flip to get 011111, or alternatively 000111.

Example 3:

1
2
3

Input: s = "00011000"
Output: 2
Explanation: We flip to get 00000000.

Solution

Method 1 - Using prefix sums

To solve the problem of making a binary string s monotone increasing with the minimum number of flips, we can use dynamic programming and prefix counting:

  1. Count Prefix Sums:
    • Maintain two variables, flips_0_to_1 and flips_1_to_0, which represent the minimum flips required to make the string monotone increasing by considering the characters 0 and the characters 1.
    • Iterate through each character of the string s.
  2. Transitions:
    • For each character:
      • If it is '0', then any 1 before it needs to be flipped to 0.
      • If it is '1', then add the minimum of current flips_0_to_1 (keeping 1 as 1) or flips_1_to_0 (flipping 0 to 1).
  3. Final Result:
    • The final result will be the minimum value between flips_0_to_1 and flips_1_to_0 after iterating through the string.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

public class Solution {
    public int minFlipsMonoIncr(String s) {
        int flips_0_to_1 = 0; 
        int flips_1_to_0 = 0;
        
        for (char ch : s.toCharArray()) {
            if (ch == '0') {
                flips_1_to_0 = Math.min(flips_0_to_1, flips_1_to_0) + 1;
            } else {
                flips_1_to_0 = Math.min(flips_0_to_1, flips_1_to_0);
                flips_0_to_1++;
            }
        }
        
        return Math.min(flips_0_to_1, flips_1_to_0);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def minFlipsMonoIncr(self, s: str) -> int:
        flips_0_to_1: int = 0
        flips_1_to_0: int = 0
        
        for ch in s:
            if ch == '0':
                flips_1_to_0 = min(flips_0_to_1, flips_1_to_0) + 1
            else:
                flips_1_to_0 = min(flips_0_to_1, flips_1_to_0)
                flips_0_to_1 += 1
        
        return min(flips_0_to_1, flips_1_to_0)

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the string s. This is because we perform constant-time operations for each character in the string.
  • 🧺 Space complexity: O(1), since we are only using a constant amount of extra space for the variables flips_0_to_1 and flips_1_to_0.