⚡Flashcard Drill➔
NeetCode #744LC-926Medium2-D Dynamic Programming
← Back to All Problems

#744 · #926 · Flip String to Monotone Increasing(将字符串翻转到单调递增)

📌 Problem Statement & Constraints

Given a binary string s, return the minimum number of flips so that the string becomes monotone increasing (some prefix of zeros followed by a suffix of ones). Constraints: 1 <= s.length <= 10^5.

💡 Core Algorithmic Approaches

  1. Scan left to right tracking ones, the number of 1s seen so far, and flips, the minimum flips for the prefix.
  2. On a 1, nothing is forced: increment ones, since that 1 is part of the ones-suffix.
  3. On a 0, there are two options: flip every earlier 1 to 0 (cost ones), or flip this 0 to 1 (cost flips + 1). Take the smaller.
  4. flips is then the answer for the whole string, because every split point between zeros and ones is considered implicitly.

💻 Benchmark Python3 Implementation

class Solution:
    def minFlipsMonoIncr(self, s: str) -> int:
        ones = 0                       # 1s seen so far
        flips = 0                      # min flips to make the prefix monotone
        for ch in s:
            if ch == "0":
                flips = min(ones, flips + 1)
            else:
                ones += 1
        return flips

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): a single pass with constant work per character.
💾 Space Complexity
O(1): two counters.

⚠️ Interview Pitfalls & Follow-ups

  • Assuming the result must be all zeros or all ones: any split point (zeros then ones) is allowed, so the DP must weigh every prefix.
  • Confusing ones with the answer: ones is only the cost of turning the prefix into all zeros; at a 0 it is one of two competing options.
  • Starting flips at 1: it starts at 0, and the very first character never needs a flip.
  • Writing an O(n^2) DP over split points: the single-pass recurrence computes the same minimum in O(n).
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related 2-D Dynamic Programming Problems