b_lc_使字符串平衡的最少删除次数（前后递推）

删除一个只函字符a、b的字符串，使其变为按字典序升序的最少删除次数

思路：f[i]表示将s的前i个字符变为全a的操作次数，g[i]类似

const int N=1e5+5;
int f[N],g[N]; 
class Solution {
public:
    int minimumDeletions(string s) {
        int n=s.size();
        for (int i=1; i<=n; i++) {
            f[i]=f[i-1], g[i]=g[i-1];
            if (s[i-1]!='a') f[i]++;
            if (s[i-1]!='b') g[i]++;
        }
        int mi=0x3f3f3f3f;
        for (int i=0; i<=n; i++) {
            mi=min(mi, f[i]+g[n]-g[i]);
        }
        return mi;
    }
};