题目

思路

一句话：把“最多改 k 次”翻译成“窗口里除众数外的字符不超过 k 个”，用滑动窗口维护这个量。

最直白的做法：枚举每个子串 [i, j]，数一遍各字母出现的次数，再看“会不会超 k 次替换”。如果每查一个子串都重新数一遍，是 O(n³)；枚举首尾时用增量维护计数，也要 O(n²)。而 n = 105，O(n²) 已经不可接受。

关键观察：对一个子串，要把它变成“同一个字母”，最优策略是保留出现次数最多的那个字母，把其余字母全改掉。设窗口长度 len、窗口内最高频字母出现 maxFreq 次，那么：

需要的替换次数 = len − maxFreq

所以一个窗口可行，当且仅当 len − maxFreq ≤ k。我们不再需要知道“具体改成谁”，只需要两个信息：窗口长度和窗口内最高频次。

再想如何找“最长”：用两个指针 left / right 维护窗口。右指针每前进一格，len 变大，len − maxFreq 只会更“难”满足；一旦它超过 k，就让左指针右移，把窗口缩回合法范围。对固定的右端点，左端点越靠右，窗口越短、越容易合法，因此从左到右收缩恰好能找到“以该右端点结尾的最长合法窗口”。

字母只有 26 个，用 count[26] 记录频次即可；左右指针各自最多移动 n 次，整体 O(n)。

解法

用 count[26] 记录大写字母出现次数，left 为窗口左端点，maxCount 为历史最高频次（后面会解释为什么不需要每次都重算当前窗口最高频次）：

1. 右指针 right 每轮先把 s[right] 计入 count，并更新 maxCount。
2. 若 窗口长度 − maxCount > k，说明这个长度还装不下，把左端字符从窗口移除，left 右移一格。
3. 用当前窗口长度更新答案 ans。

以 s = "AABBA", k = 1 为例走一遍（窗口列是每轮处理完成后的状态）：

任何窗口要合法，都需要 len − max ≤ k；上表最终答案 3（例如 "AAB" 或 "ABB" 都能一次替换变全同）。

下图把上面 3 个步骤串成流程，并逐步演示：