求解思路
这道题与其考虑"替换哪些字符",不如想"保留哪些字符"。
我们要找的是一个最短的连续子串,这个子串里包含了所有"多余"的字符,只要把这个子串替换掉,剩下的字符串自然就平衡了。
首先统计每种字符的出现次数,如果某个字符出现次数超过了 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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
public static int balancedString(String str) {
int n = str.length();
int[] s = new int[n];
int[] cnts = new int[4];
// 字符映射并统计频次: Q->0, W->1, E->2, R->3
for (int i = 0; i < n; i++) {
char c = str.charAt(i);
s[i] = c == 'W' ? 1 : (c == 'E' ? 2 : (c == 'R' ? 3 : 0));
cnts[s[i]]++;
}
// 计算每种字符的"债务"(多余量)
int debt = 0;
for (int i = 0; i < 4; i++) {
if (cnts[i] < n / 4) {
cnts[i] = 0; // 不足的字符无需处理
} else {
cnts[i] = n / 4 - cnts[i]; // 转为负数表示多余量
debt -= cnts[i]; // 累计总债务
}
}
// 如果已经平衡,直接返回
if (debt == 0) {
return 0;
}
// 滑动窗口找最短替换子串
int ans = Integer.MAX_VALUE;
for (int l = 0, r = 0; r < n; r++) {
// 右边界扩展,收集多余字符
if (cnts[s[r]]++ < 0) {
debt--;
}
// 债务清零时,尝试收缩左边界
if (debt == 0) {
while (cnts[s[l]] > 0) {
cnts[s[l++]]--;
}
ans = Math.min(ans, r - l + 1);
}
}
return ans;
}
|
如果觉得有帮助，欢迎点赞、关注、转发~