A string of '0's and '1's is monotone increasing if it consists of some number of '0's (possibly 0), followed by some number of '1's (also possibly 0.)
We are given a string S of '0's and '1's, and we may flip any '0' to a '1' or a '1' to a '0'.
Return the minimum number of flips to make S monotone increasing.
 

Example 1:
Input: "00110"
Output: 1
Explanation: We flip the last digit to get 00111.


Example 2:
Input: "010110"
Output: 2
Explanation: We flip to get 011111, or alternatively 000111.


Example 3:
Input: "00011000"
Output: 2
Explanation: We flip to get 00000000.

 
Note:

1 <= S.length <= 20000
S only consists of '0' and '1' characters.

Difficulty: interview

Starter code:

class Solution:
    def minFlipsMonoIncr(self, S: str) -> int:
        

Solutions:
class Solution:
    def minFlipsMonoIncr(self, S: str) -> int:
        onesSoFar = 0
        partial = 0
        
        for n in S:
            if n == '0':
                partial = min(onesSoFar, partial+1)      
            else:
                onesSoFar += 1
        
        return partial


class Solution:
    def minFlipsMonoIncr(self, S: str) -> int:
        
        if not S:
            return 0
        
        n = len(S)
        if n == 1:
            return 0
        
        total_1s = 0
        total_0s = 0
        for char in S:
            if char == '1':
                total_1s += 1
            else:
                total_0s += 1
        
        if total_1s == 0 or total_0s == 0:
            return 0
        
        prefix_sum = 0
        ans = float('inf')
        for i in range(n):
            prefix_sum += 1 if S[i] == '1' else 0
            ans = min(ans, prefix_sum + ((n - i - 1) - (total_1s - prefix_sum)))
        return min(ans, total_0s, total_1s)

class Solution:
    def minFlipsMonoIncr(self, S: str) -> int:
        at0 = 0
        at1 = 0
        
        num0 = 0
        for a in S:
            if a=='0':
                at1 = min(at1,at0) + 1
            else:
                at1 = min(at1,at0)
                at0 += 1
                
            #print(at0,at1)
        return min(at1,at0)

class Solution:
    def minFlipsMonoIncr(self, S: str) -> int:
        str_len = len(S)
        count_arr = [[0,0] for x in range(str_len)]
        one_start_idx = -1
        for i in range(len(S)):
            if S[i]=='0':
                if i==0:
                    count_arr[i][0] +=1
                    count_arr[i][1] = 0
                else:
                    count_arr[i][0] = count_arr[i-1][0]+1
                    count_arr[i][1] = count_arr[i-1][1]
            else:
                if i==0:
                    count_arr[i][1] +=1
                else:
                    count_arr[i][1] = count_arr[i-1][1]+1
                    count_arr[i][0] = count_arr[i-1][0]
                
                if one_start_idx == -1:
                    one_start_idx = i
       
        total_flips = []
        total_flips.append(min(count_arr[str_len-1][0], count_arr[str_len-1][1]))
        
        for i in range(one_start_idx, str_len):
            if i==0:
                total_flips.append(count_arr[str_len-1][0]-count_arr[i][0])
            elif i==str_len-1:                    
                total_flips.append(count_arr[str_len-1][0])
                        
            else:
                total_flips.append(count_arr[i-1][1]+count_arr[str_len-1][0]-count_arr[i][0])
                
                
                
                           
                           
   
                
            
            
        return min(total_flips)    
            
                      


class Solution:
    def minFlipsMonoIncr(self, S: str) -> int:
        dp = 0
        ones = 0

        for c in S:
            if c == '0':
                # 結尾為 1 的翻法的最小步驟數 = 1 + dp[i-1]
                # 結尾為 0 的翻法的最小步驟數 = 前面 1 的個數
                # 所以 dp[i] = min(1 + dp[i-1], # of 1s)
                dp = min(1 + dp, ones)
            else:
                # 結尾為 1 的翻法的最小步驟數 = dp[i-1]
                # 結尾為 0 的翻法的最小步驟數 = 1 + 前面 1 的個數
                # 所以 dp[i] = min(dp[i-1], 1 + # of 1s)
                dp = min(dp, 1 + ones)
                ones += 1

        return dp


class Solution:
    def minFlipsMonoIncr(self, S: str) -> int:
        # n = len(S)
        # zero = [0 for i in range(n)]
        # one = [0 for i in range(n)]
        # zero[0] = int(S[0])
        # one[0] = 1 - zero[0]
        # for i in range(1, n):
        #     if S[i] == '1':
        #         one[i] = min(one[i-1], zero[i-1])
        #         zero[i] = zero[i-1] + 1
        #     elif S[i] == '0':
        #         one[i] = min(one[i-1], zero[i-1]) + 1
        #         zero[i] = zero[i-1]
        # return min(zero[n-1], one[n-1])
        
        flip, one = 0, 0
        for i in S:
            if i == '1':
                one += 1
            else:
                flip += 1
            flip = min(one, flip)
        return flip

class Solution:
    def minFlipsMonoIncr(self, S: str) -> int:
        
        n, prefix, total, res = len(S), 0, S.count('1'), sys.maxsize
        for i in range(n + 1):
            res = min(res, prefix + len(S) - i - total + prefix)
            if i < n: prefix += 1 if S[i] == '1' else 0
        return res