Minimum Number of Flips to Make the Binary String Alternating

You are given a binary string s. You are allowed two operations: Type-1 moves the first character to the end of the string, and Type-2 flips any character (0 to 1 or 1 to 0). The goal is to return the minimum number of Type-2 operations you need to make s alternating, after performing any number of Type-1 operations.

An alternating binary string is one where no two adjacent characters are the same, like "010101..." or "101010...".

This is LeetCode 1888: Minimum Number of Flips to Make the Binary String Alternating.

Why this problem matters

At first glance, this looks like a brute force simulation problem. You might try all possible rotations, check each one against both alternating patterns, and track the minimum flips. That works, but it is O(n^2). The real lesson here is a technique that shows up across many string and array problems: double the string to simulate all rotations, then slide a window across the doubled string. Once you see this pattern, you can apply it to any problem where circular rotations matter.

The brute force approach

The most direct approach tries every rotation. For each rotation, compare against both target patterns and count mismatches.

def minFlips_brute(s):
    n = len(s)
    best = n
    for rot in range(n):
        rotated = s[rot:] + s[:rot]
        for target_start in [0, 1]:
            flips = 0
            for i in range(n):
                expected = (target_start + i) % 2
                if int(rotated[i]) != expected:
                    flips += 1
            best = min(best, flips)
    return best

There are n rotations, and for each one you scan all n characters against two patterns. That gives O(n^2) time. For strings up to length 100,000, this will time out.

The waste is obvious: each rotation only differs from the previous one by removing the first character and appending it to the end. You are recomputing almost everything from scratch on every iteration.

The key insight: double the string to simulate rotations

Here is the trick. Instead of actually rotating s, concatenate s with itself to form s + s. Now every rotation of the original string appears as a contiguous substring of length n inside this doubled string.

For example, if s = "111000", the doubled string is "111000111000". A window of size 6 starting at index 0 gives "111000" (rotation 0). Starting at index 1 gives "110001" (rotation 1). Starting at index 2 gives "100011" (rotation 2). And so on. Every rotation is just a different window position.

Now the problem reduces to: slide a window of size n over the doubled string, and for each window position, count how many characters differ from each target alternating pattern. Track the minimum across all positions.

You can maintain the mismatch counts incrementally. When the window slides one position to the right, one character enters and one character leaves. Update the two mismatch counters in O(1). The entire pass over the doubled string takes O(n) time.

Walking through it step by step

Let's trace through s = "111000" with n = 6. The doubled string is "111000111000". The two full-length target patterns are "010101010101" (starting with 0) and "101010101010" (starting with 1).

At window position 0, the substring "111000" has 4 mismatches against "010101" and 2 mismatches against "101010". At position 3, the substring "000111" has 2 mismatches against "010101" and 4 against "101010". The minimum across all window positions and both patterns is 2. That is the answer.

The sliding window avoids recomputing all n mismatches from scratch at each position. When the window shifts right by one, you check whether the new character entering the window matches its target position and whether the character leaving the window was a mismatch. Each shift is O(1), and you make n shifts total.

The complete solution

def minFlips(s):
    n = len(s)
    s = s + s
    target1 = ""
    target2 = ""
    for i in range(len(s)):
        target1 += str(i % 2)
        target2 += str((i + 1) % 2)

    diff1 = 0
    diff2 = 0
    result = n

    for i in range(len(s)):
        if s[i] != target1[i]:
            diff1 += 1
        if s[i] != target2[i]:
            diff2 += 1
        if i >= n:
            if s[i - n] != target1[i - n]:
                diff1 -= 1
            if s[i - n] != target2[i - n]:
                diff2 -= 1
        if i >= n - 1:
            result = min(result, diff1, diff2)

    return result

Here is what each piece does:

1. Double the string. s = s + s creates all rotations as contiguous windows.
2. Build both target patterns. target1 alternates "0101..." and target2 alternates "1010..." over the full length of the doubled string.
3. Slide the window. For each index i, add the new character's mismatches to diff1 and diff2. When i >= n, subtract the character leaving the window. Once we have a full window (i >= n - 1), record the minimum.

The two counters diff1 and diff2 track mismatches against the two patterns for the current window. They are updated in O(1) per step.

Complexity analysis

You iterate through 2n characters once, doing O(1) work per character. The target strings take O(n) space each, and the doubled string takes O(n) space. You can optimize space by computing target characters on the fly with i % 2 and (i + 1) % 2 instead of storing the full target strings, but the time complexity stays the same.

Building blocks

This problem decomposes into two reusable pieces:

1. String doubling for rotations

Whenever a problem says "move the first character to the end" or "consider all rotations," concatenate the string with itself. Every rotation of the original string appears as a window of size n in the doubled string. This converts a circular problem into a linear one.

s = s + s

This same trick appears in Repeated Substring Pattern (LeetCode 459), where you check if s exists inside s + s after removing the first and last characters.

2. Sliding window mismatch count

Maintain a running count of mismatches as the window slides. When a character enters the window, check if it matches the target and update the counter. When a character leaves, reverse that check. This gives O(1) per window shift instead of O(n) for recounting from scratch.

if s[i] != target[i]:
    diff += 1
if i >= n:
    if s[i - n] != target[i - n]:
        diff -= 1

This pattern applies to any problem where you need to track a property of a fixed-size window and update it incrementally.

Edge cases

Before submitting, verify your solution handles these:

• Already alternating. If s = "0101", no flips are needed. The answer is 0.
• Single character. s = "0" or s = "1". Any single character is already alternating. The answer is 0.
• All same characters. s = "0000" requires 2 flips (to make "0101" or "1010"). s = "00000" requires 2 flips as well ("01010" needs 2 flips from any rotation).
• Odd length. When n is odd, the two target patterns are not just reverses of each other. For n = 5, "01010" and "10101" differ at every position. Rotations matter more here because they change which pattern is cheaper.
• Even length. When n is even, Type-1 operations do not help. Every rotation of an even-length string has the same mismatch count against each pattern. The answer is just min(diff1, diff2) without any rotation. But the algorithm handles this correctly anyway.
• Length 2. s = "00" needs 1 flip, s = "11" needs 1 flip, s = "01" and s = "10" need 0 flips.

Common mistakes

1. Forgetting to double the string. If you only check the original string against both patterns, you miss rotations that could reduce the flip count. For odd-length strings, rotations can give a strictly better answer.

2. Building new strings for each rotation. Constructing s[rot:] + s[:rot] for each rotation is O(n) per rotation and O(n^2) total. The doubling trick avoids this entirely.

3. Not tracking both target patterns. An alternating string can start with either 0 or 1. If you only check one pattern, you might miss the optimal answer. Always compare against both "0101..." and "1010...".

4. Off-by-one on the window condition. The window is valid once you have seen n characters, which happens at index n - 1 (0-indexed). Using i >= n instead of i >= n - 1 skips the first valid window and can produce a wrong answer.

From understanding to recall

You now understand the string-doubling trick and the sliding window mismatch counter. The combination turns an O(n^2) rotation search into an O(n) linear pass. But the details are easy to forget: doubling s before iterating, building target patterns over the doubled length, the i >= n condition for subtracting the leaving character, and the i >= n - 1 condition for recording results. Those are exactly the kinds of small-but-critical details that slip away under pressure. Spaced repetition drills them into long-term memory so you can reconstruct the full solution from scratch when it matters.

Related posts

• Sliding Window Maximum - Classic sliding window technique
• Minimum Window Substring - Sliding window with constraint tracking
• Repeated Substring Pattern - Another problem that uses string doubling

The string-doubling plus sliding window combination is one of the most elegant tricks in competitive programming. Once you internalize it, a whole class of circular rotation problems becomes routine. CodeBricks helps you lock in these patterns through targeted practice at spaced intervals, so the next time you see a rotation problem, the approach comes to mind immediately.