题目描述
leetcode 中等题
有一个只含有 ‘Q’, ‘W’, ‘E’, ‘R’ 四种字符，且长度为 n 的字符串。
假如在该字符串中，这四个字符都恰好出现 n/4 次，那么它就是一个「平衡字符串」。
给你一个这样的字符串 s，请通过「替换一个子串」的方式，使原字符串 s 变成一个「平衡字符串」。
你可以用和「待替换子串」长度相同的 任何 其他字符串来完成替换。
请返回待替换子串的最小可能长度。
如果原字符串自身就是一个平衡字符串，则返回 0。
示例1：
1
2
3
| 输入：s = "QQWE"
输出：1
解释：我们需要把一个 'Q' 替换成 'R'，这样得到的 "RQWE" (或 "QRWE") 是平衡的。
|
提示1：
1
2
3
| 1 <= s.length <= 10^5
s.length 是 4 的倍数
s 中只含有 'Q', 'W', 'E', 'R' 四种字符
|
滑动窗口
一个关键的结论是 代替换子串 区间外的其他元素，必须满足 $cnt[Q/W/E/R] <= n/4$ ，否则显然无法替换得到一个平衡字符串。
那么我们可以通过滑动窗口得到 代替换子串 区间，并取该区间最小长度即可。
具体来说，初始时左右指针均指向 $0$ 下标处，右指针每次右移一位，直到满足区间外的元素 $cnt[Q/W/E/R] <= n/4$ ，显然此时在左指针不变的情况下，右指针没必要继续右移，因为这只会增加区间的长度，所以此时尝试将左指针右移，直到不满足条件，在这个过程中维护一个满足条件的区间长度最小值即为答案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public int balancedString(String s) {
int n = s.length();
Map<Character, Long> cnt = s.chars().mapToObj(__ -> (char)__)
.collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
if(check(cnt, n)){
return 0;
}
int ans = n;
for(int left = 0, right = 0; left < n && right < n; right++){
cnt.compute(s.charAt(right), (key, value) -> --value);
while(left < n && left <= right && check(cnt, n)){
ans = Math.min(ans, right - left + 1);
cnt.compute(s.charAt(left++), (key, value) -> ++value);
}
}
return ans;
}
private boolean check(Map<Character, Long> cnt, int n){
return cnt.values().stream().allMatch(count -> count <= n / 4);
}
}
|