题目大意：
替换子串得到平衡字符串
有一个只含有 'Q', 'W', 'E', 'R' 四种字符，且长度为 n 的字符串。
假如在该字符串中，这四个字符都恰好出现 n/4 次，那么它就是一个「平衡字符串」。
给你一个这样的字符串 s，请通过「替换一个子串」的方式，使原字符串 s 变成一个「平衡字符串」。
你可以用和「待替换子串」长度相同的 任何 其他字符串来完成替换。
请返回待替换子串的最小可能长度。
如果原字符串自身就是一个平衡字符串，则返回 0。
示例 1：
输入：s = "QWER" 输出：0 解释：s 已经是平衡的了。
示例 2：
输入：s = "QQWE" 输出：1 解释：我们需要把一个 'Q' 替换成 'R'，这样得到的 "RQWE" (或 "QRWE") 是平衡的。
示例 3：
输入：s = "QQQW" 输出：2 解释：我们可以把前面的 "QQ" 替换成 "ER"。
示例 4：
输入：s = "QQQQ" 输出：3 解释：我们可以替换后 3 个 'Q'，使 s = "QWER"。
提示：
1 <= s.length <= 10^5s.length是4的倍数s中只含有'Q','W','E','R'四种字符
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1234
解题思路分析：
如果要想达到平衡，必须保证字符串中的每种字符个数相同，也就是 'Q', 'W', 'E', 'R' 四种字符的个数分别占有四分之一。因此，四种字符中个数超过四分之一的部分都是需要被替换掉的，我们只要统计出每种字符多余的数量，然后再找到一个区间，只要区间内包含这些多余数量的字符，该区间即是一个候补解，比如字符串中多余2个Q及3个R，这时区间[i, j]之内正好包含2个Q和3个R(也有可能还包含其他2种元素)，说明我们可以将区间内的Q和R替换成其他缺失的字符来达到字符串平衡(区间内其他元素保持不变)，因此该区间算一个符合条件的解，但不一定是最优。所以需要遍历所有区间，满足条件的最小区间长度即为返回值。
遍历所有区间时我们可以采用双指针（Sliding-window）的方式，初始时，左右两个指针都在字符串的首位，循环开始后，逐步向右移动右指针，当区间外每种字符的个数均小于等于四分之一时，说明可以在当前区间内加入其他缺失的部分后可以让字符串达到平衡，因此当前区间可作为一个候补解。这时开始向右移动左指针，当区间外不能满足每种字符的个数均小于等于四分之一时，再转换移动右指针，直到结束为止，找到一个最小区间即可。
实现代码:
public int balancedString(String s) {
int length = s.length() / 4; // 每种字符的标准数量
int[] count = new int[26]; // 每种字符出现次数
char[] arr = s.toCharArray();
for (char c : arr) { // 统计每种字符出现次数
count[c - 'A']++;
}
// isValid方法用来判断每种字符的数量是否小于等于标准数量
if (isValid(count, length)) {
return 0;
}
int res = s.length(); // 返回结果
int left = 0; // 左指针，初始为0
// 循环字符串。i为右指针
// 当前区间为[left, i]，当前字符为i
for (int i = 0; i < arr.length; i++) {
// 当前字符数量减一
// 减一的目的是为了统计当前区间外每种字符的个数
count[arr[i] - 'A']--;
// 如果区间外每种字符的数量小于等于标准数量
if (isValid(count, length)) {
// 当前区间可能为一个候补解
res = Math.min(res, i - left + 1);
// 向右移动左指针
for (int j = left; j <= i; j++) {
// 移除区间的字符个数加一
count[arr[j] - 'A']++;
left++; // 左指针向右移动一位
// 如果当前区间外为合理
if (isValid(count, length)) {
// 当前区间可能为一个候补解
res = Math.min(res, i - left + 1);
} else {
// 当前区间外不合理，结束移动左指针
// 返回移动右指针i
break;
}
}
}
}
return res;
}
// 判断移除区间内元素后，每种字符的数量是否小于等于标准数量
boolean isValid(int[] count, int length) {
return count[4] <= length
&& count[16] <= length
&& count[17] <= length
&& count[22] <= length;
} 本题解法执行时间为11ms。
Runtime: 11 ms, faster than 88.15% of Java online submissions for Replace the Substring for Balanced String.
Memory Usage: 37.8 MB, less than 100.00% of Java online submissions for Replace the Substring for Balanced String.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1234-replace-the-substring-for-balanced-string-解题思路分析/