公司网站建设 意义北京网站优化站优化

给你一个字符串 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'​ 。​

来源：力扣（LeetCode）

链接：https://leetcode.cn/problems/minimum-deletions-to-make-string-balanced

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我觉得这是一道挺典型的前缀和的题目，但是是假前缀和->如果你想节省空间的话，不用全记。

首先思考人类是怎么做这道题的。

枚举吗？枚举什么？

前a后b，枚举的是断点。

假设我们确定了断点是i这个位置，假设[0,i-1]是a，[i,end]是b，怎么计算要删除多少？

=>[0,i-1]中b的个数+[i,end]中a的个数。

那每次统计i点需要删除多少的时候需要重新统计a和b的个数吗？不需要，只需要根据当前的数决定谁加谁减就可以了。

b是正序前缀和，a是逆序前缀和。

class Solution {
public:int minimumDeletions(string s) {int l=s.length();if(l==1){return 0;}int conta=0;int contb=0;if(s[l-1]=='a'){conta=1;}if(s[0]=='b'){contb=1;}for(int i=l-2;i>=0;--i){if(s[i]=='a'){conta++;}  }int cont=conta;if(s[0]=='a'){conta--;}for(int i=1;i<l;++i){cont=min(cont,conta+contb);if(s[i]=='b'){contb++;}else{conta--;}}cont=min(cont,contb);return cont;}
};

但是感觉两次循环还是得有的，毕竟方向不一样。

动态规划的方法是我最开始的思路，但是我想不通也写不出来，现在还没看懂，谁给我仔细讲讲。。。