NeetCode #236LC-1888MediumSliding Window
← Back to All Problems#236 · #1888 · Minimum Number of Flips to Make the Binary String Alternating(使二进制字符串字符交替的最少反转次数)
📌 Problem Statement & Constraints
You are given a binary string
s. In one step you may either remove the first character and append it to the end, or flip any character. Return the minimum number of flips to make the string alternating. Constraints: 1 <= s.length <= 10^5.💡 Core Algorithmic Approaches
- Because rotations are free, every cyclic rotation of
sis reachable; the problem is to find the rotation whose mismatch count against an alternating pattern is minimal. - For each rotation offset, the mismatch count against the
0101...pattern is what we need; the count against1010...is its complementn - count. - Build a doubled array and use prefix sums over two indicator arrays: one for even offsets and one for odd offsets (the parity alignment shifts with the offset).
- Take the minimum over all rotations and both patterns.
💻 Benchmark Python3 Implementation
class Solution:
def minFlips(self, s: str) -> int:
n = len(s)
arr = [int(s[i % n]) for i in range(2 * n)]
# A[i]: mismatch with the "0101..." pattern when the offset is even
# B[i]: mismatch when the offset is odd (parity alignment flips)
prefA = [0] * (2 * n + 1)
prefB = [0] * (2 * n + 1)
for i in range(2 * n):
a = 1 if arr[i] != i % 2 else 0
prefA[i + 1] = prefA[i] + a
prefB[i + 1] = prefB[i] + (1 - a)
res = n
for st in range(n): # rotation offset
if st % 2 == 0:
m0 = prefA[st + n] - prefA[st]
else:
m0 = prefB[st + n] - prefB[st]
res = min(res, m0, n - m0) # also consider the complementary pattern
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): the doubled arrays and prefix sums are linear, and each rotation is checked in O(1).
💾 Space Complexity
O(n) for the doubled array and prefix sums.
⚠️ Interview Pitfalls & Follow-ups
- Ignoring rotations: the free rotation operation is what makes this harder than the plain alternating-string problem.
- Forgetting the complementary pattern: for each rotation, both
0101...and1010...are candidates, and their counts sum ton. - Using the same parity alignment for odd and even offsets: shifting the window by one flips which pattern aligns with the absolute index parity, hence the two prefix arrays.
- Simulating each rotation explicitly: O(n^2).
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🧩 Related Sliding Window Problems
#219 · #219Contains Duplicate II#220 · #121Best Time to Buy and Sell Stock#221 · #2379Minimum Recolors to Get K Consecutive Black Blocks#222 · #1984Minimum Difference Between Highest and Lowest of K Scores#223 · #1343Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold#224 · #1052Grumpy Bookstore Owner