746. Fewest Flips to Put the Zeros First
A binary string is SORTED when every 0 comes before every 1. One flip changes a single
character. Print the fewest flips that make the string sorted.
00110 -> 1
010110 -> 2
111000 -> 3
000111 -> 0
## Every sorted string is described by one number
A sorted string is a run of zeros followed by a run of ones, so it is completely determined by
where the boundary sits. There are n + 1 choices, from "all ones" to "all zeros".
Once the boundary is fixed the cost is forced:
cost(cut) = (ones strictly before the cut) + (zeros at or after the cut)
because every one before the boundary must become a zero, and every zero after it must become a one.
Turning "make it sorted" into "choose a boundary" is the whole step. What is left is a minimum
over n + 1 numbers.
## Both counts are prefix and suffix tallies
The ones before a cut is a running prefix count. The zeros at or after it is a suffix count, and a suffix count is just the total minus the prefix. So one sweep produces both:
ones = 0
zerosAfter = total zeros in the string
best = zerosAfter # the cut at position 0
for each character:
if it is '1': ones += 1
else: zerosAfter -= 1
best = min(best, ones + zerosAfter)
Recomputing the two counts per cut is O(n^2) and gives the same answer.
## The cut before the first character must be considered
Seeding best with zerosAfter before the loop IS that cut: it turns every zero into a one
and costs nothing else. Starting the minimum inside the loop instead silently forbids the
all-ones answer.
On 111000 the best cut is at position 0 for a cost of 3, tying with the cut at the end. On a
string of all ones the answer is 0 and only the cut at position 0 finds it.
## Why the updates go where they do
Inside the loop the character just consumed is BEFORE the next cut, so ones must be
incremented before the comparison, and zerosAfter must be decremented before it too. Doing
either afterwards shifts the whole sweep by one position.
## Boundaries
An already sorted string answers 0. A single character always answers 0.
## Cost
Time O(n). Space O(1).
Constraints - `1 ≤ length ≤ 200000` - every character is `0` or `1`
Input
One line containing the binary string.
Output
Print one integer, the fewest flips needed to make the string sorted.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.