Along a stretch of coastline, n buoys are anchored in a straight line and numbered from the shore outward. Each buoy flashes either a safe signal (0) or a hazard signal (1). Maritime policy requires the chain of buoys to be coherent: every safe buoy must appear before every hazard buoy along the line, so the signals read as a block of 0s followed by a block of 1s (either block may be empty).
Given the buoys' current signals as a binary string, the harbor crew may flip any buoy's signal (safe becomes hazard, or hazard becomes safe) at a cost of one action per buoy flipped. Determine the minimum number of flips needed to make the chain coherent.
A single line containing a string s of length n, made only of the characters 0 and 1 — the buoys' current signals, read from shore outward.
A single integer: the minimum number of buoys that must be flipped so the chain becomes coherent.
s consists only of the characters '0' and '1'Example 1
Input
00110
Expected
1
Explanation
The chain reads safe, safe, hazard, hazard, safe — not coherent, because a safe buoy follows two hazard buoys. Flipping just the last buoy (from 0 to 1) gives 00111, a block of safe buoys followed by a block of hazard buoys — coherent with only 1 flip, the minimum possible.
Example 2
Input
1111
Expected
0
Explanation
All four buoys already show hazard, which is trivially an empty block of safe buoys followed by a block of 4 hazard buoys — already coherent, so 0 flips are needed.
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 →