每日一题：使字符串平衡的最少删除次数 - 刷题题解

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

根据题目意思，最后字符串应该是 1）全是 a，2）全是 b，所有的 a 都在 b 的前面（即：aaaaaaaaabbbbbbb）

那么，可以枚举分割点来计算删除的最小字符数：

从左往右枚举 n + 1 个分割点，针对每一个分割点，左边必须全 a，右边必须全 b，两边删除的字符数求和就是点前分割点分割，达到平衡的删除字符数；如此取最小的即可
优化：
- 先统计从右到左子字符串中所有 a 的字符串，记录与数组

	class Solution {
	public int minimumDeletions(String s) {
	char[] chs = s.toCharArray();
	int n = chs.length;
	// [i, n - 1] 的 a 的数量
	int[] racount = new int[n];
	for (int i = n - 1; i >= 0; --i) {
	racount[i] = chs[i] == 'a' ? 1 : 0;
	if (i < n - 1) {
	racount[i] += racount[i + 1];
	}
	}

	// 左边 b 的数量
	int lbcount = 0;
	int res = Integer.MAX_VALUE;
	// 枚举每一个分割点
	for (int i = 0; i < n; ++i) {
	// [0, i) 为 a，[i, n - 1] 为 b
	res = Math.min(res, lbcount + racount[i]);
	lbcount += chs[i] == 'b' ? 1 : 0;
	}

	return Math.min(lbcount, res);
	}
	}