An airport ground crew is inspecting a straight row of n runway beacon lights. Each beacon is currently lit in one of two colors, and the whole row is given as a string s of length n made only of the characters '0' and '1', where '0' marks one color and '1' marks the other. Aviation safety rules require that beacon colors strictly alternate along the row — no two adjacent beacons may be lit in the same color.
The crew can recolor any beacon by flipping its character (changing a '0' to '1' or a '1' to '0'). Determine the minimum number of beacons that must be flipped so that the resulting row strictly alternates.
A single line containing the binary string s.
Print a single integer: the minimum number of flips required to make s strictly alternating.
Example 1
Input
0001
Expected
1
Explanation
Comparing "0001" to the pattern "0101" (mismatches at positions 2 and... actually only position 2, a single '0' vs '1' mismatch) requires 1 flip, while comparing to "1010" requires 3 flips. Flipping the second beacon turns "0001" into "0101", which strictly alternates, so the minimum is 1.
Example 2
Input
1111
Expected
2
Explanation
Comparing "1111" to the pattern "0101" gives 2 mismatches (positions 1 and 3), and comparing to "1010" also gives 2 mismatches (positions 2 and 4). Either way exactly 2 beacons must be flipped, so the minimum is 2.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →