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^5s[i]要么是a要么是b​。​分析字符串平衡时要么全是 a要么全是 b要么从某一个位置分成左右两部分时左边全为 a右边全为 b。枚举这个分成两半的位置分别统计左边有多少个 b右边有多少个 a取和的最小值即可。int minimumDeletions(char* s) { int nstrlen(s),pre_a[n5],pre_b[n5]; pre_a[0]pre_b[0]0; if(s[0]a)pre_a[0]1; else pre_b[0]1; for(int i1;in;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 ansfmin(pre_a[n-1],pre_b[n-1]); for(int i1;in-1;i) ansfmin(pre_b[i-1]pre_a[n-1]-pre_a[i-1],ans); return ans; }