Solution
Approach 1: Prefix Sums
Intuition
For say a 5 digit string, the answer is either '00000'
, '00001'
, '00011'
, '00111'
, '01111'
, or '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[0] + A[1] + ... + 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 Nx
ones, there are P[x]
ones in the start that must be flipped, plus (Nx)  (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 Nx
, but we want the number of zeros.
Algorithm
For example, with S = "010110"
: we have P = [0, 0, 1, 1, 2, 3, 3]
. Now say we want to evaluate having x=3
zeros.
There are P[3] = 1
ones in the first 3 characters, and P[6]  P[3] = 2
ones in the later Nx = 3
characters.
So, there is (Nx)  (P[N]  P[x]) = 1
zero in the later Nx
characters.
We take the minimum among all candidate answers to arrive at the final answer.
Complexity Analysis

Time Complexity: , where is the length of
S
. 
Space Complexity: .
Analysis written by: @awice.