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

题目：

给你一个字符串 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的最大数量。

其次，我们进行2次遍历，统计出来ab最大字符串的个数。

最后，用字符串总长度减去这个最大的个数，即可得到最终的结果。

代码：

class Solution {
public:int minimumDeletions(string s) {int n = s.size();int maxab = 0;vector lefta(n,0);vector rightb(n,0);lefta[0] = s[0] == 'a' ? 1 : 0;rightb[n - 1] = s[n - 1] == 'b' ? 1 : 0;for(int i = 1;i < n;i++){if(s[i] == 'a')lefta[i] = lefta[i-1] + 1;elselefta[i] = lefta[i-1];}for(int i = n-2;i >= 0;i--){if(s[i] == 'b')rightb[i] = rightb[i+1] + 1;elserightb[i] = rightb[i+1];}for(int i = 0;i < n;i++)maxab = max(maxab,lefta[i] + rightb[i]);return n - maxab;}
};