Every evening the harbor nightwatch inspects a row of n lanterns strung along the sea wall, each lantern glowing either dim (marked '0') or bright (marked '1'). During one maintenance pass, a technician may choose any subset of the lanterns, unclip exactly those chosen lanterns from their brackets, and reclip them back onto the very same brackets — in their original left-to-right order — arranged so that, among just the chosen lanterns, every dim one sits left of every bright one; every lantern the technician did not choose stays exactly as it was. The nightwatch supervisor wants a single maintenance pass, touching the fewest lanterns possible, that leaves the WHOLE row sorted: every dim lantern strictly to the left of every bright lantern. Given the row, determine the minimum number of lanterns that must be included in that one pass.
Line 1: an integer n, the number of lanterns. Line 2: a string s of length n consisting only of the characters '0' (dim) and '1' (bright) — the current state of the row, left to right.
A single integer: the minimum number of lanterns that must be selected in one maintenance pass so that, after reclipping the selected lanterns into ascending (dim-before-bright) order at their own original positions, the entire row reads as all dim lanterns followed by all bright lanterns.
1 <= n <= 200000 s consists only of the characters '0' and '1'.
Example 1
Input
5 10010
Expected
2
Explanation
With 3 dim and 2 bright lanterns, the fully sorted target row is "00011". Comparing s="10010" against the target position by position, they differ only at position 1 (s has '1' where the target wants '0') and position 5 (s has '0' where the target wants '1'). Selecting exactly those two lanterns and reclipping them (their characters '1' and '0' sorted ascending become '0' then '1') turns the row into "00011", and every other lantern already matched the target. No single lantern can be selected alone, since that would leave the other mismatch untouched, so the minimum is 2.
Example 2
Input
6 111000
Expected
6
Explanation
The row is completely reversed: three bright lanterns first, then three dim ones, while the sorted target is "000111". Every one of the 6 positions differs from the target (position 1 has '1' vs target '0', and so on through position 6), so all 6 lanterns must be included in the pass — selecting any fewer would leave at least one mismatched lantern untouched, and untouched lanterns never change value.
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 →