926. Flip String to Monotone Increasing

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.

• Time : O(n)
• Space : O(1)
• if this solution is little hard to understand then see second solution
• it builds up from second one

class Solution {
public:
    int minFlipsMonoIncr(string s) {
        int n = s.length(), res = 0;
        for(int i = n - 1, count = 0; i >= 0; i--) {
            if(s[i] == '0') count++;
            if(s[i] == '1') {
                res = min(count, 1 + res);
            }
        }
        return res;
    }
};

• Time : O(n)
• Space : O(n)

class Solution {
    int helper(string& s, vector<int>& A, int p) {
        if(p == s.length()) return 0;
        if(s[p] == '0') return helper(s, A, p + 1);
        return min(A[p], 1 + helper(s, A, p + 1));
    }
public:
    int minFlipsMonoIncr(string s) {
        int n = s.length();
        vector<int> counter(n);
        for(int i = n - 1, count = 0; i >= 0; i--) {
            if(s[i] == '0') count++;
            counter[i] = count;
        }
        return helper(s, counter, 0);
    }
};