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
- Scan left to right tracking
ones, the number of1s seen so far, andflips, the minimum flips for the prefix. - On a
1, nothing is forced: incrementones, since that1is part of the ones-suffix. - On a
0, there are two options: flip every earlier1to0(costones), or flip this0to1(costflips + 1). Take the smaller. flipsis 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
oneswith the answer:onesis only the cost of turning the prefix into all zeros; at a0it is one of two competing options. - Starting
flipsat 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.