替换后的最长重复字符：滑动窗口与最大频次维护

适读人群：Java 后端工程师、算法中阶学习者 | 阅读时长：约 17 分钟 | 难度：⭐⭐⭐

---

开篇故事

LeetCode 424 是我认为最能考察"滑动窗口深度理解"的题目之一，因为它的合法性判断条件相当不直观。

窗口合法的条件是：窗口长度 - 窗口内出现频次最高的字符数 <= k。换句话说，窗口内"其他字符"的数量不超过 k（最多替换 k 次把它们都改成出现频次最高的字符）。

很多人能背下这个条件，但没搞清楚"为什么只需要维护最大频次"，以及"收缩窗口时为什么不需要重新计算最大频次"。今天把这两个问题都讲透。

---

一、题目解析

题目（LeetCode 424）： 给你一个字符串 s 和一个整数 k，可以选择字符串中的任一字符，并将其更改为任何其他大写英文字符，最多可以进行 k 次操作。执行上述操作后，返回包含相同字母的最长子字符串的长度。

示例：

• s = "ABAB"，k = 2，输出：4（把两个 A 换成 B，或两个 B 换成 A）
• s = "AABABBA"，k = 1，输出：4

窗口合法条件： 窗口长度 - 窗口内最高频次 <= k（最少需要替换的次数不超过 k）

---

二、解法一：暴力枚举 O(n²)

public class Solution1 {
    public int characterReplacement(String s, int k) {
        int n = s.length(), maxLen = 0;
        for (int i = 0; i < n; i++) {
            int[] freq = new int[26];
            int maxFreq = 0;
            for (int j = i; j < n; j++) {
                freq[s.charAt(j) - 'A']++;
                maxFreq = Math.max(maxFreq, freq[s.charAt(j) - 'A']);
                // 合法条件：(j - i + 1) - maxFreq <= k
                if ((j - i + 1) - maxFreq <= k) {
                    maxLen = Math.max(maxLen, j - i + 1);
                }
            }
        }
        return maxLen;
    }
}

复杂度分析

• 时间复杂度：O(n²)。
• 空间复杂度：O(1)（字母表大小是常数）。

---

三、解法二：滑动窗口（直观版，每步完整重算）

public class Solution2 {
    public int characterReplacement(String s, int k) {
        int[] freq = new int[26];
        int left = 0, maxLen = 0;

        for (int right = 0; right < s.length(); right++) {
            freq[s.charAt(right) - 'A']++;

            // 每次完整计算最大频次
            int maxFreq = 0;
            for (int f : freq) maxFreq = Math.max(maxFreq, f);

            // 如果不合法，收缩窗口
            while ((right - left + 1) - maxFreq > k) {
                freq[s.charAt(left) - 'A']--;
                left++;
                // 重新计算（这里每步重算，O(26)）
                maxFreq = 0;
                for (int f : freq) maxFreq = Math.max(maxFreq, f);
            }

            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }
}

复杂度分析

• 时间复杂度：O(26n)，即 O(n)。每步重算最大频次 O(26)。
• 空间复杂度：O(1)。

---

四、解法三最优：滑动窗口 + maxFreq 只增不减技巧

核心技巧：为什么 maxFreq 只需要增不需要减？

这是这道题最精妙的地方。

观察： 我们想找的是最大的窗口，使得 windowLen - maxFreq <= k，即 windowLen - k <= maxFreq。

当 maxFreq 增大时，窗口可以更大，所以 maxFreq 只有在增大时才有意义（贡献到了更长的答案）。

当我们收缩窗口时，maxFreq 可能减小，但减小后的 maxFreq 对应一个不大于当前已记录答案的窗口，不需要更新答案。

更严格地说： 整个算法过程中，我们只需要知道"历史最大的 maxFreq 是多少"（因为我们在寻找最长的合法窗口）。如果当前窗口的 maxFreq 低于历史最大值，那么当前窗口长度不会超过历史最优答案（因为需要替换更多字符），不需要更新 maxLen。

所以：

• 当 right++ 加入新字符时，用 maxFreq = max(maxFreq, freq[newChar]) 更新。
• 当不合法时，left++ 收缩，但不更新 maxFreq（即使当前窗口的最大频次降低了，也不管它）。

这样 maxFreq 只会不断增大，永不减小，最终 maxFreq 等于整个过程中遇到的最大频次。

Mermaid 图

完整代码

public class Solution3 {
    public int characterReplacement(String s, int k) {
        int[] freq = new int[26];
        int left = 0;
        int maxFreq = 0;  // 历史最大频次（只增不减）

        for (int right = 0; right < s.length(); right++) {
            // 加入 right 处字符
            int c = s.charAt(right) - 'A';
            freq[c]++;
            // 更新最大频次（只取 max，不在收缩时减小）
            maxFreq = Math.max(maxFreq, freq[c]);

            // 如果窗口不合法：需要替换的字符数 > k
            if ((right - left + 1) - maxFreq > k) {
                // 收缩左端（不更新 maxFreq）
                freq[s.charAt(left) - 'A']--;
                left++;
            }
            // 注意：这里不用 while，因为每次最多收缩一步
            // 原因：每次 right 右移至多让窗口增大1，不合法时至多收缩1即可恢复
        }

        // 循环结束时，窗口长度 right - left 就是最大合法窗口长度
        // 因为 maxFreq 只增不减，窗口长度维持最大合法尺寸
        return s.length() - left;
    }

    public static void main(String[] args) {
        Solution3 sol = new Solution3();
        System.out.println(sol.characterReplacement("ABAB", 2));    // 4
        System.out.println(sol.characterReplacement("AABABBA", 1)); // 4
        System.out.println(sol.characterReplacement("AAAA", 2));    // 4
        System.out.println(sol.characterReplacement("ABCDE", 1));   // 2
    }
}

为什么这里用 if 而不是 while？

这是一个常见问题。前面 209 题用了 while 来尽量收缩，这里为什么用 if？

因为这里的窗口大小是"单调增"的——每次 right++ 最多增加 1，不合法时 if 最多减少 1（left++），窗口大小最多保持不变。我们追求的是最大窗口，所以窗口大小一旦收缩了，后续窗口需要更大才有意义，不需要反复收缩。

用 if 代替 while 保证了窗口长度单调不减（或等于），直接用 s.length() - left 就是答案。

复杂度分析

• 时间复杂度：O(n)。right 和 left 各移动最多 n 次。
• 空间复杂度：O(1)（26 个字母计数数组）。

---

五、举一反三

题号	题目	相似点
1004	最大连续 1 的个数 III	最多替换 k 个 0，求最长 1 的子数组
2024	考试的最大困扰度	最多替换 k 个字符，求最长同字符子串
340	至多包含 K 种字符的最长子串	维护不同字符数

---

六、踩坑实录

坑一：认为 maxFreq 需要在收缩时重新计算

这是最常见的误解。收缩时不更新 maxFreq 是一种"懒惰优化"——我们知道即使 maxFreq 降低了，当前窗口对应的答案也不会超过历史最优（窗口长度受 maxFreq 制约），所以降低了的 maxFreq 根本不会被用到。不更新是安全的，而且省了 O(26) 的重算开销。

坑二：把窗口合法条件搞反

(windowLen - maxFreq) <= k 是合法条件，> k 是不合法条件。有人把两者搞反，导致窗口不合法时不收缩，合法时反而收缩。

坑三：只有一种字符时的边界

比如 s = "AAAA"，k = 2，maxFreq 最终等于 4，4 - 4 = 0 <= 2，答案是 4，正确。全相同字符时不需要替换，算法自然处理。

坑四：最终答案的取法

这个解法最终答案是 s.length() - left，这是因为窗口大小（right - left）在循环结束时等于最大合法窗口长度。但有人在循环里每步都更新 maxLen = right - left + 1，这也是正确的，只是多做了一些更新操作。两种写法等价。

---

七、总结

LeetCode 424 展示了滑动窗口的一个重要技巧：在某些情况下，窗口状态的某些量只需要单调更新，不需要在收缩时精确维护。这种"懒惰"是因为：我们只关心"更大的窗口"，对当前窗口的精确状态不在意——只要窗口大小不超过历史最优，就直接跳过。

maxFreq 只增不减，是这道题的精华所在。理解了这个，你就真正理解了滑动窗口里状态维护的灵活性。