Flip String to Monotone Increasing

medium string dp prefix sum

Problem

Given a binary string s, return the minimum number of flips to make it monotone increasing (all 0s, then all 1s).

Inputs = "00110"

Output1

Pick a split index i; answer = min(ones_before_i + zeros_after_i).

s (binary)

def minFlipsMonoIncr(s):
    ones = flips = 0
    for c in s:
        if c == '1': ones += 1
        else: flips = min(flips + 1, ones)
    return flips

function minFlipsMonoIncr(s) {
  let ones = 0, flips = 0;
  for (const c of s) {
    if (c === '1') ones++;
    else flips = Math.min(flips + 1, ones);
  }
  return flips;
}

class Solution {
    public int minFlipsMonoIncr(String s) {
        int ones = 0, flips = 0;
        for (char c : s.toCharArray()) {
            if (c == '1') ones++;
            else flips = Math.min(flips + 1, ones);
        }
        return flips;
    }
}

int minFlipsMonoIncr(string s) {
    int ones = 0, flips = 0;
    for (char c : s) {
        if (c == '1') ones++;
        else flips = min(flips + 1, ones);
    }
    return flips;
}

Explanation

A monotone increasing binary string is all 0s followed by all 1s. To get there we either flip some 1s to 0, or some 0s to 1. This solution scans the string once and tracks the cheapest way as it goes.

We keep two numbers: ones counts how many 1s we have seen so far, and flips is the minimum flips needed to make everything seen so far monotone.

When we see a 1, we just add it to ones — it can stay as a trailing one for free. When we see a 0, we have a choice: flips = min(flips + 1, ones). The first option flips this 0 into a 1 (cost +1); the second option keeps it as a 0 but then we must flip every earlier 1 (that's ones flips).

Example: s = "00110". The two leading zeros are free, the two ones bump ones to 2, then the final 0 gives min(flips + 1, ones) = min(1, 2) = 1. So one flip is enough.

One pass, two counters, so it is O(n) time and O(1) space.

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