Minimum Number of Flips to Make Binary String Alternating
mediumTime: 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).
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.
Easy way to go wrong
Forgetting that the string is effectively circular — rotations are achieved by considering the doubled string.