A binary string is monotone increasing if it consists of some number of 0's (possibly none), followed by some number of 1's (also possibly none).

You are given a binary string s. You can flip s[i] changing it from 0 to 1 or from 1 to 0.

Return the minimum number of flips to make s monotone increasing.

&nbsp;
Example 1:

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


Example 2:

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


Example 3:

Input: s = "00011000"
Output: 2
Explanation: We flip to get 00000000.


&nbsp;
Constraints:


	1 &lt;= s.length &lt;= 105
	s[i] is either '0' or '1'.


class Solution:
    def minFlipsMonoIncr(self, s: str) -> int:
        n = len(s)
        min_flip = n
        one_left = 0
        # zero_right = 0
        # for c in s:
        #     if c == "0":
        #         zero_right += 1
        
        zero_right = s.count("0") # since we will start with 11...11 then every zero in s will be on the right side of the border
        
        # for each i imagine that we have the borderline at i index any index >= i will be 1 and index < i will be 0.
        # i = 0, n = 5 -> 11111
        # i = 1, n = 5 -> 01111
        # i = 5        -> 00000
        for i in range(n + 1):
            # the number of flip will be equal number of 1 on the left side of the border + number of zero on the right side of the border
            # from example     00110
            #                    v 
            # comparing with   00111  : i = 2, one_left = 0, zero_right = 1, then we have to do 0 + 1 flip in this i
            min_flip = min(min_flip,one_left+zero_right)
            
            # edge case for i = n or all zero (00...00)
            if i == len(s):
                continue
            # reduce count of zero_right when 0 is moving to the 0-zone or left side of border
            if s[i] == "0":
                zero_right -= 1
            else:
                one_left += 1 # increase one on the left side when we move 1 into the left side
        
        return min_flip
            
            
class Solution {
    public int minFlipsMonoIncr(String s) {
        int n = s.length();
        int zeroToOne =0;
        int countOfOnes=0;
        for(int i=0;i<n;i++)
        {
            if(s.charAt(i)=='0')
                zeroToOne=Math.min(zeroToOne+1,countOfOnes);
            else
                countOfOnes=countOfOnes+1;
        }
        return zeroToOne;
        
    }
}
class Solution {
public:
    int minFlipsMonoIncr(string s) {
        //assume start making 1 from i th index
        // what number of 0s we need to flip at right side
        // what number of 1s we need to flip at left side
        // for this maintain prefix and suffix

        int n = s.size();
        vector<int> noOfZerosToRight(n,0); // R to L
        vector<int> noOfOnesToLeft(n,0); // L to R

        if(s[0] == '1') noOfOnesToLeft[0] = 1;
        for(int i=1;i<n;i++){
            if(s[i] == '1') noOfOnesToLeft[i] = noOfOnesToLeft[i-1] + 1;
            else noOfOnesToLeft[i] = noOfOnesToLeft[i-1];
        }

        if(s[n-1] == '0') noOfZerosToRight[n-1] = 1;
        for(int i=n-2;i>=0;i--){
            if(s[i] == '0') noOfZerosToRight[i] = noOfZerosToRight[i+1] + 1;
            else noOfZerosToRight[i] = noOfZerosToRight[i+1];
        }

        // starting treating i as partition of 0 and 1:
        // 0 at the lefts and 1 at the rights including i:
        int ans = 1e9;
        for(int i=0;i<n;i++){
            int leftFlips = 0; //when we want all 1s
            int rightFlips = noOfZerosToRight[i];

            if(i-1 >= 0) leftFlips = noOfOnesToLeft[i-1];
            ans = min(ans, (leftFlips + rightFlips));
        }

        ans = min(ans, noOfOnesToLeft.back() + 0); //when want all 0s
        return ans;
    }
    //O(N) + O(N)
};
function getPrefixSumArray(s) {
    const prefixSumOfOnes = Array(s.length).fill(0);
    
    let currentSum = 0;
    for (let x = 0; x < s.length; x++) {
        if (s[x] === '1')
            currentSum++;
        
        prefixSumOfOnes[x] = currentSum;
    }
    
    return prefixSumOfOnes;
}

var minFlipsMonoIncr = function(s) {
    const prefixSumOfOnes = getPrefixSumArray(s);
    
    let answer = prefixSumOfOnes[s.length - 1]; // Case where we want to change to '0000'
    
    for (let x = 0; x < s.length; x++) {
        const sizeOfRightHandSide = s.length - x;
        let numChangesRequired = null;
        
        if (x === 0) { 
            // Case where we want to change to '1111'
            const numOfOnesToChangeToZero = 0;
            
            const numOfOnesOnRightHandSide = prefixSumOfOnes[s.length - 1];
            const numOfZerosToChangeToOne = sizeOfRightHandSide - numOfOnesOnRightHandSide;
            
            numChangesRequired = numOfOnesToChangeToZero + numOfZerosToChangeToOne;
        }
        else { 
            // Cases like '0111', '0011', '0001'
            const numOfOnesToChangeToZero = prefixSumOfOnes[x - 1];
            
            const numOfOnesOnRightHandSide = prefixSumOfOnes[s.length - 1] - prefixSumOfOnes[x - 1];
            const numOfZerosToChangeToOne = sizeOfRightHandSide - numOfOnesOnRightHandSide;
            
            numChangesRequired = numOfOnesToChangeToZero + numOfZerosToChangeToOne;
        }
        
        answer = Math.min(answer, numChangesRequired);
    }
    
    return answer;
};
Flip String to Monotone Increasing