问题链接
问题描述
给你一个字符串 s ，它仅包含字符 a 和 b 。
你可以删除 s 中任意数目的字符，使得 s 平衡 。当不存在下标对 (i,j) 满足 i < j ，且 s[i] = b 的同时 s[j]= a ，此时认为 s 是 平衡 的。
请你返回使 s 平衡 的 最少 删除次数。
示例
输入：s = "aababbab"
输出：2
解释：你可以选择以下任意一种方案：
下标从 0 开始，删除第 2 和第 6 个字符（"aababbab" -> "aaabbb"），
下标从 0 开始，删除第 3 和第 6 个字符（"aababbab" -> "aabbbb"）。
输入：s = "bbaaaaabb"
输出：2
解释：唯一的最优解是删除最前面两个字符。
解题思路
一眼动态规划
A. 找到重复性子问题：字符串的前n位组成的子字符串，求此时的最长平衡字符串；
B. 存储中间状态: dp[2]
第一位表示全a的最大长度，第二位表示可以接b的字符串的最大长度（末尾可能是A，可能是B）。
C. 找到dp方程（在此不再赘述，可以直接看代码示例）
代码示例（JAVA）
class Solution {
public int minimumDeletions(String s) {
int len = s.length();
// 第一位表示全A的最大长度，第二位表示可以接B的字符串的最大长度（末尾可能是A，可能是B）
int[] dp = new int[2];
for (int i = 0; i < len; i++) {
char c = s.charAt(i);
if (c == 'a') {
dp[0] = dp[0] + 1;
dp[1] = Math.max(dp[0], dp[1]);
} else {
dp[1] = Math.max(dp[0], dp[1] + 1);
}
}
return len - Math.max(dp[0], dp[1]);
}
}
时间复杂度：O(n)
