LeetCode 424. 替换后的最长重复字符
题目描述
题意分析
字符串只包含大写英文字母，最多可以把
k个位置的字符替换成任意大写字母。要求找到一段连续子串，使它能在预算内变成全部由同一种字符组成，并返回最大长度。不要求真的修改字符串，也不要求整串都相同。对于长度为
length的候选子串，保留其中出现次数最多的字符、替换其余字符最省操作，所以最少需要替换length - 最高频次个位置。
解法：滑动窗口
核心思路
[!blue]
用左右指针维护窗口，
freq保存当前窗口各字符的实际频次。右端每加入一个字符，就更新它的次数，再判断窗口长度是否能被允许的替换次数支撑。代码里的
maxCount刻意只增不减：它保存扫描过程中出现过的最高频次，不一定等于缩窗后的真实最高频次。若窗口长度 - maxCount > k，就移出左端字符；调整后把窗口长度用于更新答案。为什么历史值不会导致漏解？它始终不小于当前真实最高频次，因此上述条件成立时，按真实频次计算也一定需要超过
k次替换。这个判据只会比真实条件宽松，不会把一个本来合法的窗口判成非法；真正可行的更长子串不会因此被跳过。为什么保留了不合法的位置，也不会夸大答案？每次右端只增加一个字符，而
maxCount不下降，所以一轮最多需要移出一个左端字符，窗口长度只会保持或增加。一旦发生缩窗，调整后的长度恰好为maxCount + k；此后只要maxCount不变，继续加入字符就只能同时移出一个字符，长度不会再增长。历史频次变得陈旧正是因为移出了左端字符，而这时算法只保留此前达到过的长度。若之后窗口要创造更长答案，
maxCount必须再次提高；提高时，当前窗口确实刚增加到这么多个同字符，且长度满足预算，所以这个新长度对应一个真实合法窗口。第一次缩窗之前，窗口一直只扩不缩，最高频次也始终真实。因此，陈旧的
maxCount可能让窗口位置不再合法，却只会保留旧的最优长度，不能产生虚假的更大答案。这份实现适合返回长度，不能直接把最后保留的窗口内容当成答案。
解题步骤
- 初始化 26 项频次表、左端
left、历史最高频次maxCount和答案。- 从左到右扩展
right，增加新字符频次，必要时提高maxCount。- 当
right - left + 1 - maxCount > k时，减少左端字符频次并右移left；不下调历史最高频次。- 用调整后的窗口长度更新答案，扫描完成后返回最大长度。
代码实现
class Solution {
public int characterReplacement(String s, int k) {
int[] freq = new int[26];
int left = 0;
// 保存历史最高频次，缩窗后允许陈旧
int maxCount = 0;
int ans = 0;
for (int right = 0; right < s.length(); right++) {
int idx = s.charAt(right) - 'A';
freq[idx]++;
maxCount = Math.max(maxCount, freq[idx]);
while (right - left + 1 - maxCount > k) {
freq[s.charAt(left) - 'A']--;
left++;
}
// 更新可达到的长度，当前保留位置不一定真实合法
ans = Math.max(ans, right - left + 1);
}
return ans;
}
}
func characterReplacement(s string, k int) int {
freq := make([]int, 26)
left := 0
// 保存历史最高频次，缩窗后允许陈旧
maxCount := 0
ans := 0
for right := 0; right < len(s); right++ {
idx := s[right] - 'A'
freq[idx]++
if freq[idx] > maxCount {
maxCount = freq[idx]
}
for right-left+1-maxCount > k {
freq[s[left]-'A']--
left++
}
// 更新可达到的长度，当前保留位置不一定真实合法
if right-left+1 > ans {
ans = right - left + 1
}
}
return ans
}
复杂度分析
设字符串长度为 $n$。
- 时间复杂度：$O(n)$。左右指针都只向右移动，每个字符至多加入、移出一次。
- 辅助空间复杂度：$O(1)$，字符集固定为 26 个大写字母。
关键点总结
[!green]
- 窗口变成同一字符的最少替换次数，等于长度减去真实最高频次。
- 代码保留的是历史最高频次，它给出更宽松的长度界，不能标注成当前窗口的精确值。
- 历史值陈旧时只维持旧长度，创造更长答案时必有真实频次作为依据。
- 返回长度正确，不代表最终保留的位置一定合法。
易错点总结
[!yellow]
- 缩窗时直接执行
maxCount--，会破坏历史值定义；移出一个字符也不意味着真实最高频次必然下降。- 频次表仍必须准确增减，只有
maxCount允许陈旧，不能连窗口实际计数也不维护。- 替换数量是长度减去保留字符的次数，不能写成相加，也不是窗口内不同字符的种类数。
- 不要根据最终
left、right返回具体子串，这份历史最大值写法只保证最大长度。k == 0仍允许已有的同字符连续段，答案不应直接设为零。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1004. 最大连续1的个数 III | 中等 | 同样把修改次数变成窗口预算，原题只翻0，本题可选某个最高频字符作为统一目标。 |
| 340. 至多包含 K 个不同字符的最长子串 | 中等 | 同样维护字符窗口，但本题预算是长度减最高频次数，原题预算是不同字符种数。 |
| 1208. 尽可能使字符串相等 | 中等 | 维护窗口内可消耗的修改预算；本题预算为窗口长度减最大字符频次，该题预算为对应字符差值之和。 |
| 2024. 考试的最大困扰度 | 中等 | 维护窗口内可消耗的修改预算；本题预算为窗口长度减最大字符频次，该题分别计算统一为两种答案时的窗口。 |