前后缀分解
可以在原字符串相邻的两个字符之间划一条间隔，然后分别计算左右字符串的某个值，最终结果即为左右结果和
1. 示例题
给你一个字符串 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
解释：唯一的最优解是删除最前面两个字符。
解
function minimumDeletions(s: string): number {
let leftB = 0
let rightA = 0
for (let i = 0; i < s.length; i++) {
if (s[i] === 'a') {
rightA++
}
}
let ans = leftB + rightA
for (let i = 0; i < s.length; i++) {
switch (s[i]) {
case 'a':
rightA--
break
case 'b':
leftB++
break
}
ans = Math.min(ans, leftB + rightA)
}
return ans
}
2. 题目
-
使字符串平衡的最少删除次数。题解中有更多相关题链接