Minimum Flips to Make Binary String Alternating — Circular Window (LC 1888)

Problem Statement#

LeetCode 1888 — Minimum Number of Flips to Make the Binary String Alternating (Medium)

You are given a binary string s. You may perform type-1 operations (rotate leftmost character to the right end) any number of times, then type-2 operations (flip any character). Return the minimum number of type-2 flips to make the string alternating.

Constraints:

• 1 <= s.length <= 10^5
• s[i] is '0' or '1'

Input:  s = "111000"
Output: 2

Input:  s = "010"
Output: 0

Why This Problem Matters#

This problem is a beautiful application of the circular sliding window trick. Rotation is notoriously tricky to handle directly — but by doubling the string, all rotations become consecutive windows of length n in s + s. Instead of actually rotating, you slide a fixed-size window and count mismatches with each of the two possible alternating targets.

The doubling-to-handle-circularity technique appears across competitive programming and FAANG interviews. Mastering it here prepares you for circular buffer problems, circular array rotations, and string pattern matching on circular sequences. It is the cleaner alternative to modulo indexing when you need to view the entire rotation simultaneously.

The Core Insight#

There are exactly two valid alternating patterns:

• t1 = "010101..." (starts with 0)
• t2 = "101010..." (starts with 1)

A rotation by r positions transforms s into doubled[r : r+n] where doubled = s + s. So the problem reduces to: slide a window of length n over doubled and find the window with the fewest mismatches against t1 or t2.

Maintain two running mismatch counts (diff1, diff2) and update them in O(1) as the window slides. The target character at position i is i % 2 for t1 and (i+1) % 2 for t2 — no need to build explicit target strings.

Visual Dry Run#

Input: s = "111000", n = 6, doubled = "111000111000"

Initial window [0,5] = "111000":

• diff1 = 4 (mismatches vs "010101"), diff2 = 2 (mismatches vs "101010")

Sliding window right: add new character at position n, subtract character at position 0.

Minimum across all windows = 2

Solution (Optimal)#

def minFlips(s: str) -> int:
    n = len(s)
    doubled = s + s
 
    diff1 = 0   # mismatches vs "010101..."
    diff2 = 0   # mismatches vs "101010..."
 
    for i in range(n):
        if doubled[i] != str(i % 2):
            diff1 += 1
        if doubled[i] != str((i + 1) % 2):
            diff2 += 1
 
    ans = min(diff1, diff2)
 
    for i in range(n, 2 * n):
        if doubled[i] != str(i % 2):
            diff1 += 1
        if doubled[i] != str((i + 1) % 2):
            diff2 += 1
 
        left = i - n
        if doubled[left] != str(left % 2):
            diff1 -= 1
        if doubled[left] != str((left + 1) % 2):
            diff2 -= 1
 
        ans = min(ans, diff1, diff2)
 
    return ans

var minFlips = function(s) {
    const n = s.length;
    const doubled = s + s;
    let diff1 = 0, diff2 = 0;
 
    for (let i = 0; i < n; i++) {
        if (doubled[i] !== String(i % 2)) diff1++;
        if (doubled[i] !== String((i + 1) % 2)) diff2++;
    }
 
    let ans = Math.min(diff1, diff2);
 
    for (let i = n; i < 2 * n; i++) {
        if (doubled[i] !== String(i % 2)) diff1++;
        if (doubled[i] !== String((i + 1) % 2)) diff2++;
 
        const left = i - n;
        if (doubled[left] !== String(left % 2)) diff1--;
        if (doubled[left] !== String((left + 1) % 2)) diff2--;
 
        ans = Math.min(ans, diff1, diff2);
    }
    return ans;
};

Time: O(n) — two passes each O(n) Space: O(n) — doubled string; reducible to O(1) using s[i % n]

Common Mistakes#

• Building explicit target strings of length 2n — unnecessary; compute i % 2 on the fly
• Handling the initial window separately from the sliding part — inconsistent logic; cleaner to initialize first n elements then slide
• Not recording the minimum for the initial window before the sliding loop starts
• Using n as both string length and loop bound on doubled string — doubled has length 2n; window slides from n to 2n-1
• Thinking rotations cost something — rotations are free, only flips have cost

Interview Tips#

• State the key insight immediately: "Since rotations are free, I can simulate all rotations as windows in the doubled string"
• There are only two alternating patterns — compute mismatches against both simultaneously
• The O(1) space version uses s[i % n] instead of building doubled — mention it as a follow-up
• This doubles-the-string trick is the standard template for any problem where circular shifts are free

Follow-up Questions#

• O(1) space: access s[i % n] instead of building doubled; all other logic identical
• No rotations allowed: just count mismatches vs t1 and t2 directly — O(n), no window
• More than two alternating patterns: maintain one diff counter per target pattern; same sliding logic

Key Takeaways#

• Double the string to convert all rotations into fixed-length windows — the canonical circular sliding window trick
• There are exactly two valid alternating binary patterns; compute mismatches against both simultaneously
• Maintain running mismatch counts diff1, diff2 and update in O(1) per slide step
• Target character at position i is i % 2 for pattern 1 and (i+1) % 2 for pattern 2 — no explicit target strings needed
• Minimum across all window positions and both patterns is the answer
• Space can be reduced to O(1) by using s[i % n] instead of doubled = s + s