Problem Statement in English

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.

Monotone increasing means that for all i <= j, s[i] <= s[j].

So a string like "000111" is monotone increasing, while "001010" is not. Also, "000" and "111" are monotone increasing.

Approach

The intuitive solution to this is simply to try every possible partition of the string into two parts: the left part being all 0s and the right part being all 1s. Along with that, we also need to consider the edge cases where the entire string is all 0s or all 1s.

This solution can be implemented using prefix and suffix sums.

But the crazy solution is both less intuitive and way less code.

The idea is that we can build the solution for any index i based on the solution for index i-1.

Think about it. If we know the minimum flips until the previous index, can we arrive at the number of flips when we include the current index?

Note that we’re not looking for the string itself, just the number of flips. This makes it easier. Tricky.

So, let’s try all cases:

  • If the current character is 1, then we don’t need to do anything. The number of flips remains the same as before. This is because any string ending in 1 is valid as long as the prefix is valid. Take for example 000111 or 00111 or 1111. All valid.

  • If the current character is 0, then we have two choices:

    1. Flip this 0 to 1. In this case, the number of flips increases by 1 compared to the previous index.

    2. Keep this 0 as is. But for this to be valid, we need to ensure that all previous characters are also 0s. This means we need to flip all previous 1s to 0s. The number of flips in this case would be equal to the number of 1s encountered so far.

So in reality, we just need to keep track of two things as we iterate through the string:

  1. The number of 1s encountered so far.
  2. The minimum number of flips calculated so far.

Reading the code will make this clearer.

Solution in Python

  • Straighforward Prefix-Suffix Sum Solution

class Solution:
    def minFlipsMonoIncr(self, s: str) -> int:
        N = len(s)

        otl = [0] * N
        zfh = [0] * N
        zfh[-1] = int(s[-1] == "0")

        ones = zeroes = 0
        res = N

        for i in range(1, N):
            otl[i] = otl[i - 1] + int(s[i - 1] == "1")

        for i in reversed(range(N - 1)):
            zfh[i] = zfh[i + 1] + int(s[i] == "0")

        for c in s:
            if c == "1":
                ones += 1
            else:
                zeroes += 1

        # everything until and excluding this point be 0, and everything else be 1
        for i in range(N):
            res = min(res, otl[i] + zfh[i])

        # everything be 0
        res = min(res, N - ones)
        
        # everything be 1
        res = min(res, N - zeroes)
    
        return res
  • Optimal Dynamic Programming Solution

class Solution:
    def minFlipsMonoIncr(self, s: str) -> int:
        N = len(s)
        ones = 0
        res = N

        for c in s:
            if c == "1":
                ones += 1
            else:
                res = min(ones, res + 1)

        return min(res, N - ones)

Complexity

  • Time: O(N)O(N)
    Since we are iterating through the string only once.

  • Space: O(1)O(1)
    We are using only a constant amount of extra space.

Mistakes I Made

I had to look up the optimal solution. It was not intuitive to me at all.

And we are done.