LeetCode 424. 替换后的最长重复字符

2026-07-24 HGNULB 约 6 分钟

文章信息 9 个分类 3 个标签

分类

题目描述

✅ 424. 替换后的最长重复字符

题意分析

输入是一个只含大写英文字母的字符串 s 和一个整数 k。允许挑最多 k 个位置，把上面的字符改成任意大写字母，问改完之后能得到的「所有字符都相同的连续子串」最长有多长。

有两点需要读清楚。第一，k 是替换次数的上限而不是必须用满，用不满也算合法。第二，答案要的是连续子串的长度，所以真正被考察的是「某一段区间能不能通过不超过 k 次替换变成同一个字符」。

把这个判定条件写出来：对一段区间，最省事的做法当然是保留出现次数最多的那种字符、把其余字符全部改掉。于是该区间可行，当且仅当「区间长度减去区间内出现次数最多的字符的个数」不超过 k。这个量正是「必须替换的字符数」。

约束里字符串长度可达 $10^5$，k 的范围是 0 到 s.length()，说明需要线性或接近线性的做法，逐段枚举区间的 $O(n^2)$ 会超时。边界上要覆盖：k = 0 时退化成求最长连续相同字符段；k 大于等于串长时整串都可以改成同一个字符，答案就是串长；空串答案为 0。

解法：滑动窗口

核心思路

对任意窗口，若其中出现次数最多的字符有 maxCount 个，最少需要替换的字符数就是
\[\text{windowSize}-\text{maxCount}.\]
因此窗口合法当且仅当这个差值不超过 k。右端点不断扩张；差值超限时右移左端点，就能在线性时间内考察所有可能成为答案的窗口。

窗口内用长度为 26 的数组计数。maxCount 只在右端点加入字符时更新，左端点移出字符时不回退，所以它表示扫描过程中见过的最大频次，未必是当前窗口的真实最大频次。这是有意为之：本题只求最大长度，不要求每一轮留下的窗口都真实合法。

设算法记录到长度 L，当时有 L - maxCount <= k。maxCount 必然曾在某个长度不超过 L 的窗口中真实出现过；将那个窗口向两侧扩成长度 L，新增位置即使全部替换，也至多需要 L - maxCount 次，因此确实存在长度为 L 的合法子串。历史值不会制造虚假的更长答案。反过来，历史值只会让收缩更晚，不会比使用当前真实最大频次时多收缩，所以也不会漏掉最优窗口。

循环不变量是：频次数组始终对应当前 [left, right]；窗口长度是截至当前右端点能保留的最大候选长度；ans 是扫描前缀中已经证明可达到的最大长度。

解题步骤

初始化频次数组、左端点 left、历史最大频次 maxCount 和答案 ans。

枚举右端点，将 s[right] 加入窗口，并用该字符的新频次更新 maxCount。

若 right - left + 1 - maxCount > k，移出 s[left] 并右移 left，直到候选宽度重新满足条件。

用当前窗口长度更新 ans，扫描结束后返回它。

以 s = "AABABBA"、k = 1 为例：扫描到前四个字符时，窗口 AABA 中 A 有 3 个，只需替换 1 个，答案更新为 4。继续加入 B 后长度变为 5，需要替换 2 个，于是左端点右移，候选长度回到 4。末尾窗口可能因历史 maxCount = 3 而不是真实合法窗口，但此前的 AABA 已证明长度 4 可达，因此最终答案仍为 4。

代码实现

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
}

复杂度分析

时间复杂度：$O(n)$。左右指针都只单调向右，每个字符至多进入和离开窗口各一次。

空间复杂度：$O(1)$。频次数组长度固定为 26。

关键点总结

窗口最少替换次数等于“窗口长度减去最高字符频次”，这是整个滑动窗口判定式。

maxCount 是历史最大频次，不要求等于当前窗口的真实众数；它只影响何时收缩，不会改变最大长度的正确性。

历史值可能保留一个当前并不合法的窗口，但不会产生不存在的更长答案，也不会漏掉合法的更长窗口。

字符集固定为 26 个大写字母，数组比哈希表更直接；若字符集不固定，再改用映射。

面试时最重要的追问是“为什么 maxCount 不回退”，应从“不造假、不漏解”两方面回答，而不是只背结论。

易错点总结

收缩条件应是 > k，不是 >= k；恰好替换 k 次仍然合法。

窗口长度是 right - left + 1，漏掉 +1 会产生边界错误。

移动左端点前必须减少对应字符的计数，否则数组不再代表当前窗口。

不要在收缩时简单执行 maxCount--；它既不一定是被移出字符的频次，也不一定只下降 1。要么保留历史值，要么重新扫描 26 个计数。

ans 应在收缩完成后更新，避免记录尚未满足判定式的长度。

本题字符均为大写字母，下标应使用 s.charAt(i) - 'A'；Go 按字节遍历也只因该字符集是单字节 ASCII。

相似题目

题目	难度	考察点
485. 最大连续 1 的个数	简单	不允许任何替换，退化成一次线性计数
1004. 最大连续1的个数 III	中等	目标字符固定为 `1`，窗口内只需数 `0` 的个数
487. 最大连续1的个数 II	中等	上题在 `k = 1` 时的特例，可用「记住上一段长度」的滚动写法
1493. 删掉一个元素以后全为 1 的最长子数组	中等	必须删掉一个元素，答案要在窗口长度上减一
面试题 05.03. 翻转数位	简单	同一模型套在二进制位上，需要处理负数的位表示
3. 无重复字符的最长子串	中等	合法性判据换成「窗口内无重复」，左指针可直接跳跃
340. 至多包含 K 个不同字符的最长子串	中等	判据是不同字符种数上限，需要维护计数表的大小