Approach 1: Prefix Sums
For say a 5 digit string, the answer is either
'11111'. Let's try to calculate the cost of switching to that answer. The answer has two halves, a left (zero) half, and a right (one) half.
Evidently, it comes down to a question of knowing, for each candidate half: how many ones are in the left half, and how many zeros are in the right half.
We can use prefix sums. Say
P[i+1] = A + A + ... + A[i], where
A[i] = 1 if
S[i] == '1', else
A[i] = 0. We can calculate
P in linear time.
Then if we want
x zeros followed by
N-x ones, there are
P[x] ones in the start that must be flipped, plus
(N-x) - (P[N] - P[x]) zeros that must be flipped. The last calculation comes from the fact that there are
P[N] - P[x] ones in the later segment of length
N-x, but we want the number of zeros.
For example, with
S = "010110": we have
P = [0, 0, 1, 1, 2, 3, 3]. Now say we want to evaluate having
P = 1 ones in the first 3 characters, and
P - P = 2 ones in the later
N-x = 3 characters.
So, there is
(N-x) - (P[N] - P[x]) = 1 zero in the later
We take the minimum among all candidate answers to arrive at the final answer.
Time Complexity: , where is the length of
Space Complexity: .
Analysis written by: @awice.