【力扣】1653. 使字符串平衡的最少删除次数【中等】

给你一个字符串 s ，它仅包含字符 'a' 和 'b'​​​​ 。

你可以删除 s 中任意数目的字符，使得 s 平衡 。当不存在下标对 (i,j) 满足 i < j ，且 s[i] = 'b' 的同时 s[j]= 'a' ，此时认为 s 是 平衡 的。

请你返回使 s 平衡 的 最少 删除次数。

示例 1：

输入：s = "aababbab"

输出：2

解释：你可以选择以下任意一种方案：

下标从 0 开始，删除第 2 和第 6 个字符（"aababbab" -> "aaabbb"），

下标从 0 开始，删除第 3 和第 6 个字符（"aababbab" -> "aabbbb"）。

示例 2：

输入：s = "bbaaaaabb"

输出：2

解释：唯一的最优解是删除最前面两个字符。

提示：

1 <= s.length <= 105

s[i] 要么是 'a' 要么是 'b'​ 。​

题解：

具有比较明显的动态规划思想，由题目可知，当所有的删除操作完成后，a应该在b之前，那么可以采用如下的方法进行动态规划：

方法一：

从头开始，给定一个空字符串，当遍历到a时，对字符串长度加1，当遍历到b时，此时可以找到上一个以a或b结尾的字符串的最大长度加1，遍历完之后，将原字符串的长度与该字符串长度相减即可。

class Solution {
public:
    int minimumDeletions(string s) {
        int n = s.size();
        int cnta = 0, cntb = 0;
        for(int i = 0; i < n; i++){
            if(s[i] == 'a'){
                cnta++;
            }
            else{
                cntb = max(cnta, cntb) + 1;
            }
        }
        return n - max(cnta, cntb);
    }
};

方法二：

这个方法更加直接，在遍历过程中，遇到b时，不考虑删除，而遇到a时，考虑删除a或者删除前面的b，每次选择删除的最小值，那么最终结果就是需要删除的次数。

class Solution {
public:
    int minimumDeletions(string s) {
        int n = s.size();
        int cnta = 0, cntb = 0;
        for(int i = 0; i < n; i++){
            if(s[i] == 'a'){
                cnta++;
            }
            else{
                cntb = max(cnta, cntb) + 1;
            }
        }
        return n - max(cnta, cntb);
    }
};