⚡Flashcard Drill➔
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

  1. Because rotations are free, every cyclic rotation of s is reachable; the problem is to find the rotation whose mismatch count against an alternating pattern is minimal.
  2. For each rotation offset, the mismatch count against the 0101... pattern is what we need; the count against 1010... is its complement n - count.
  3. 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).
  4. 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... and 1010... are candidates, and their counts sum to n.
  • 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.
🎯 Drill This Card Now➔

🧩 Related Sliding Window Problems