Description

Submission

class Solution {
public:
    int minimumDeletions(string s) {
        int ra = 0, rb = 0;

        for(char c: s) {
            if(c == 'a') ra++;
            if(c == 'b') rb++;
        }

        if(!ra || !rb) return 0;
        
        // i: end of a, inclusive
        int ret = ra;
        int lb = 0;
        for(int i = 0; i < s.size(); ++i) {
            if(s[i] == 'a') {
                ra--;
            } else {
                lb++;
            }
            ret = min(ret, lb + ra);
        }
        
        return ret;
    }
};

// aa...aabb....bb

// aababbab

Submission 220304

class Solution {
public:
    int minimumDeletions(string s) {
        vector<char> stk;

        for(char ch: s) {
            if(stk.empty() || stk.back() <= ch) {
                stk.push_back(ch);
            } else {
                auto it = upper_bound(stk.begin(), stk.end(), ch);
                *it = ch;
            }
        }

        return s.size() - stk.size();
    }
};