1653. 使字符串平衡的最少删除次数

题目链接：1653. 使字符串平衡的最少删除次数

方法：动态规划

解题思路

• 对于字符串\(s\)，设使得字符串\(s[0, i]\)平衡的最小删除次数为\(dp[i]\)。
• 若\(s[0, n - 2]\)为平衡字符串，当\(s[n-1]==b\)时，则\(dp[n-1] = dp[n-2]\)；当\(s[n-1]==a\)时，则\(dp[n-1] = min(dp[n-2] + 1\), \(a\)前面所有\(b\)的数量)。
• 从下到上利用递推实现（归），刚好可以计算当前'a'之前的'b'的数量。

代码

class Solution {
public:
    int minimumDeletions(string s) {
        int countB = 0, dp = 0;
        for (auto &c : s) {
            if (c == 'a') {
                dp = min(countB, dp + 1);
            } else {
                countB ++ ;
            }
        }
        return dp;
    }
};

复杂度分析

时间复杂度：\(O(n)\)；
空间复杂度：\(O(1)\)。