leetcode 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 <= 10^5
• s[i]要么是'a'要么是'b'​。​

分析：字符串平衡时，要么全是 a，要么全是 b，要么从某一个位置分成左右两部分时左边全为 a，右边全为 b。枚举这个分成两半的位置，分别统计左边有多少个 b，右边有多少个 a，取和的最小值即可。

int minimumDeletions(char* s) { int n=strlen(s),pre_a[n+5],pre_b[n+5]; pre_a[0]=pre_b[0]=0; if(s[0]=='a')pre_a[0]=1; else pre_b[0]=1; for(int i=1;i<n;++i) { pre_a[i]=pre_a[i-1],pre_b[i]=pre_b[i-1]; if(s[i]=='a')pre_a[i]++; else pre_b[i]++; } int ans=fmin(pre_a[n-1],pre_b[n-1]); for(int i=1;i<n-1;++i) ans=fmin(pre_b[i-1]+pre_a[n-1]-pre_a[i-1],ans); return ans; }