We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Flip String to Monotone Increasing

Difficulty: Medium

Problem Description

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.

Key Insights

  • A string is monotone increasing if all 0s appear before all 1s.
  • We can count the number of 1s to the left and the number of 0s to the right for each position in the string.
  • The goal is to find the point where the number of flips (to convert 1s to 0s on the left and 0s to 1s on the right) is minimized.
  • The problem can be solved in linear time by maintaining a running count of 0s and 1s.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve this problem, we will use a greedy approach. We will iterate through the string while maintaining a count of how many 1s have been seen so far and how many 0s are remaining. At each position, we calculate the number of flips needed to make the string monotone increasing up to that point and keep track of the minimum flips required.

Code Solutions

def minFlipsMonoIncr(s: str) -> int:
    count_ones = 0  # Count of 1's seen so far
    flips = 0       # Number of flips needed
    for char in s:
        if char == '1':
            count_ones += 1  # Increment count for 1's
        else:
            flips += 1  # Increment flips needed for current 0
        flips = min(flips, count_ones)  # Minimize flips needed
    return flips
← Back to All Questions