{x}
blog image

Flip String to Monotone Increasing

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 <= 105
  • s[i] is either '0' or '1'.

Solution Explanation: Flip String to Monotone Increasing

This problem asks for the minimum number of flips required to make a binary string monotone increasing (meaning all 0s followed by all 1s). The optimal solution uses a clever approach combining prefix sums and enumeration.

Approach:

  1. Count Zeros: First, count the total number of '0's in the input string s. This is stored in tot. This represents the minimum flips needed if we were to convert all characters to '1's.

  2. Iteration and Minimization: The core logic iterates through the string. For each position i:

    • cur: Tracks the number of '0's encountered so far. This is crucial because we're implicitly considering different points to switch from '0's to '1's.

    • ans: Stores the minimum flips found so far. We update ans in each iteration.

    • Flips Calculation: The key is calculating the flips for the current position i as the transition point. We consider two parts:

      • Left of i: All '1's before i need to be flipped to '0' to maintain the monotone increasing property. The count of these is i - cur (total positions minus '0's).
      • Right of i: All '0's after i need to be flipped to '1'. The count of these is tot - cur (total '0's minus the '0's before i).
      • Total Flips: The total flips for this position i is i - cur + tot - cur.

    • Update ans: We update ans with the minimum between the current ans and the calculated flips for the current position.

  3. Return ans: After iterating through all positions, ans holds the minimum number of flips needed.

Time and Space Complexity:

  • Time Complexity: O(n), where n is the length of the string. We iterate through the string once.
  • Space Complexity: O(1). We use only a few constant extra variables.

Code Examples (Python):

class Solution:
    def minFlipsMonoIncr(self, s: str) -> int:
        tot = s.count("0")
        ans, cur = tot, 0  # Initialize ans to the maximum possible flips (all 0s to 1s)
        for i, c in enumerate(s, 1): #enumerate with start index 1 for easier calculation
            cur += int(c == "0") # increment cur if current character is '0'
            ans = min(ans, i - cur + tot - cur) # update ans with minimum flips
        return ans

The other languages (Java, C++, Go, TypeScript, JavaScript) follow the same logic with minor syntax differences. The core algorithm remains consistent across all implementations. The use of enumerate in Python makes the code slightly more concise. The other examples use similar techniques to achieve the same effect (incrementing a counter and using array indices).