Flip String to Monotone Increasing - Video Solutions

Problem Overview: You are given a binary string s. The goal is to flip the minimum number of characters so the string becomes monotone increasing—all 0s appear before any 1s. Any character can be flipped (0 → 1 or 1 → 0), and you must return the minimum number of flips required.

Approach 1: Prefix Sum Method (O(n) time, O(n) space)

This approach tries every possible split point where the string transitions from 0s to 1s. For each index i, the left side should contain only 0s and the right side only 1s. Use prefix sums to count how many 1s appear on the left (these must flip to 0) and how many 0s appear on the right (these must flip to 1). Iterate through all split points and compute leftOnes + rightZeros. The minimum across all splits gives the answer. This technique is a classic application of string processing combined with prefix sum counting.

Approach 2: Dynamic Programming (O(n) time, O(1) space)

Track two running values while scanning the string once. Let ones count how many 1s have appeared so far, and flips represent the minimum flips required up to the current position. When you see a 1, simply increment ones because it fits the monotone pattern. When you see a 0, you have two choices: flip this 0 to 1 (cost flips + 1) or flip all previous 1s to 0 (cost ones). Update flips = min(flips + 1, ones). This greedy-style DP keeps the optimal answer for each prefix and avoids storing extra arrays. The technique is common in dynamic programming problems where decisions depend on previous states.

Recommended for interviews: The Dynamic Programming approach is usually what interviewers expect. It processes the string in one pass, uses constant space, and shows you can convert a global constraint into incremental decisions. The prefix sum approach is still valuable because it demonstrates clear reasoning about split points and counting, but the DP solution shows stronger optimization skills.