Problem Statement

Minimum Number of Flips to Make Binary String Alternating

You are given a binary string s, which just means a string made only of the characters 0 and 1. You can do two kinds of moves. Move type 1 is a rotation: take the first character off the front and stick it on the back, so "abc" becomes "bca". Move type 2 is a flip: pick any character and switch it, a 0 becomes a 1 or a 1 becomes a 0. Your goal is to make the string alternating, which means no two neighbors are the same, like "0101" or "1010". You can rotate as many times as you want for free, and the question asks for the smallest number of flips you need. The trick is this: rotating the string just shifts where the start is. If you write the string out twice in a row (s + s), then every possible rotation shows up as a chunk of length n somewhere inside that doubled string. So instead of actually rotating, we glue a copy onto the end and look at every chunk of length n. A "window" is just a chunk of the string we are looking at right now, and we slide it across to check each rotation in turn.

mediumSliding WindowSliding WindowTime: O(n) · Space: O(1)

Signals to notice

minimum flips to make binary string alternatingtwo target patternssliding window on doubled string

Brute force first

Try all rotations and count flips — O(n²).

The key insight

The string can be rotated (it's circular for the flip count). Double the string, slide a window of size n, count mismatches against both target patterns (01010... and 10101...). Minimum across all windows. O(n).

Trace it on `s="111000"`

n=6, double s -> "111000111000". Targets per index: t1="010101" (i%2), t2="101010" ((i+1)%2).
Build first window i=0..5 ("111000"): mismatches vs t1 at idx0,2,3,5 -> diff1=4; vs t2 at idx1,4 -> diff2=2. result=min(4,2)=2.
Slide right=6 ('1'): add to diff1 (idx6 wants '0')->5, diff2 (wants '1')->2. Remove left=0 ('1'): diff1->4, diff2->2. result=min(2,4,2)=2.
Slide right=7 ('1'): add diff1->4, diff2->3. Remove left=1 ('1'): diff1->4, diff2->2. result=2.
Slide right=8 ('1'): add diff1->5, diff2->2. Remove left=2 ('1'): diff1->4, diff2->2. result=2.
Continue right=9,10,11: windows stay balanced; min window flip count never drops below 2.
Return result=2 (rotate "111000"->"100011", flip 2 chars to alternating).

What must stay true

Doubling the string simulates all rotations. A sliding window of size n over the doubled string represents each rotation. Count mismatches against both alternating patterns.

Shape of the loop

double s; n = len(s)/2
diff1 = diff2 = 0; result = INF
for i in 0..len(s)-1:
    if s[i] != (i%2):     diff1 += 1   # vs "0101..."
    if s[i] != ((i+1)%2): diff2 += 1   # vs "1010..."
    if i >= n: shrink left end, decrement diff1/diff2 for s[i-n]
    if i >= n-1: result = min(result, diff1, diff2)
return result

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Forgetting that the string is effectively circular — rotations are achieved by considering the doubled string.

Sliding Window Pattern