Minimum Number of Flips to Make Binary String Alternating
mediumTime: O(n)Space: O(1)
Recognize the pattern
minimum flips to make binary string alternatingtwo target patternssliding window on doubled string
Brute force idea
Try all rotations and count flips — O(n²).
Better approach
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).
Key invariant
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.
Watch out for
Forgetting that the string is effectively circular — rotations are achieved by considering the doubled string.