@SomeBottle 在 Leetcode每日一题 —— 1653. 使字符串平衡的最少删除次数 中发帖
思路
题目的意思大概是通过删除字符,使得最后的字串中 b 的左侧只有 a 或者空,a 的右侧只有 b 或者空。
从示例中产生的结果看来,最后会形成形似 aaabbb 这样的左 a 右 b 字串,要从原字串变成这样,我需要做的是把 a 部分所有的 b 字符移除、把 b 部分所有的 a 字符移除。
于是 a 部分和 b 部分的交界处就是一个分割点,我要做的就是把分割点左侧的 b 移除,分割点右侧的 a 移除。
怎么知道每个分割点左侧和右侧有多少 b 和 a 呢?这个时候就可以算前缀 / 后缀和了。最后枚举每个分割点,找到最少要移除的字符数即可。
代码
class Solution {
public:
int minimumDeletions(string s) {
// 意思就是 b 的左侧只能有 a (或者空)
// a 的右侧全都要是 b...