你好，同学！今天我们要攻克的是一道非常经典的字符串滑动窗口题目。在 NOI 竞赛中，这类题目属于“基础算法-双指针”范畴，它能锻炼你对区间合法性的动态维护能力。

这道题在 LeetCode 上名为《替换后的最长重复字符》，但在 NOI 辅导中，我们通常称其为“约束下的最长等值子串变换问题”。

---

一、 预备知识点

1. 双指针/滑动窗口：通过 L 和 R 两个指针动态维护一个区间。
2. 词频统计：利用数组（如 cnt[26]）实时记录窗口内字符出现的次数。
3. 动态维护最值：在 $O(1)$ 或 $O(26)$ 的时间内更新当前窗口中出现频率最高的字符次数。
4. 区间补集思想：窗口长度减去最高频字符次数，即为“必须替换的最小次数”。

---

二、 题目描述 (NOI 竞赛风格)

题目名称：替换后的最长重复字符 (Longest Repeating Character Replacement)

【问题描述】 给定一个仅由大写英文字母组成的字符串 $S$，以及一个整数 $K$。 你可以选择字符串中的任意字符，并将其更改为任何其他大写英文字母。该操作最多可执行 $K$ 次。 在执行上述操作后，请找出包含重复字母的最长子串的长度。

【输入格式】 第一行包含一个字符串 $S$。 第二行包含一个整数 $K$。

【输出格式】 输出一个整数，表示满足条件的最长子串长度。

【样例 1 输入】

ABAB
2

【样例 1 输出】

4

(解释：将两个 'B' 改为 'A'，得到 "AAAA"，长度为 4。)

【样例 2 输入】

AABABBA
1

【样例 2 输出】

4

(解释：将中间的一个 'A' 改为 'B'，得到 "AABBBBA"，其中 "BBBB" 是最长子串。)

【数据规模与约定】

• $1 \le |S| \le 10^5$
• $0 \le K \le |S|$
• 字符串仅包含大写英文字母。

---

三、 启发式引导：草稿纸上的推理过程

请拿出草稿纸，我们一起来解构这个窗口。

第一步：核心判断逻辑

思考： 如果一个窗口 $[L, R]$ 能够通过最多 $K$ 次替换变成全部相同的字符，需要满足什么条件？

• 观察： 显然，我们应该保留窗口中出现次数最多的那个字符（设其次数为 maxCount），把其余字符全部换掉。
• 结论： 只要 (窗口长度 - maxCount) <= K，这个窗口就是合法的。

第二步：滑动窗口的律动

1. 右移 R：不断扩大窗口，并将新进入字符的频率加 1。
2. 更新 maxCount：记录当前窗口内出现次数最多的字符的频率。
3. 判断与左移 L：如果 (R - L + 1) - maxCount > K，说明当前的 $K$ 不够用了。
   • 注意点：此时我们需要把 $S[L]$ 移出窗口，频率减 1，并将 $L$ 右移。

第三步：关于 maxCount 的高级思考（提分点）

教练提问： 当窗口左移 $L$ 时，我们是否需要重新扫描 cnt[26] 数组来减小 maxCount？

• 启发： 我们的目标是找“最长”。只有当 maxCount 变得更大时，才可能产生比当前更长的合法窗口。所以，即便当前窗口的实际最高频次下降了，我们也不必立即更新 maxCount，因为它不会对“寻找更长的解”产生贡献。
• 结论： maxCount 可以只增不减，这可以将时间复杂度稳定在 $O(N)$。

---

四 : 算法逻辑流程图 (伪代码思路)

请根据此流程图在脑中构建 C++ 逻辑：

graph TD
    A[开始] --> B[输入字符串 S 和 K]
    B --> C[初始化: L=0, R=0, maxCount=0, cnt数组全0]
    C --> D{R < S.length?}
    D -- 是 --> E[更新 cnt[S[R]]++]
    E --> F[maxCount = max(maxCount, cnt[S[R]])]
    F --> G{窗口长度 - maxCount > K?}
    G -- 是 --> H[cnt[S[L]]--, L++]
    G -- 否 --> I[R++]
    H --> I
    I --> D
    D -- 否 --> J[输出最终窗口大小: R - L]
    J --> K[结束]

---

五、 复杂度分析与优化建议

• 时间复杂度分析：
  • R 指针从 $0$ 扫到 $N$。
  • L 指针最多也只扫到 $N$。
  • 每次移动的操作都是 $O(1)$（即使维护 maxCount 扫描 26 个字母也是常数级）。
  • 总复杂度：$O(N)$。在 $10^5$ 数据下，运行时间通常在 10ms 左右。
• 空间复杂度分析：
  • 仅需一个大小为 26 的 int 数组。
  • 总复杂度：$O(1)$ 或 $O(\Sigma)$，其中 $\Sigma$ 是字符集大小。
• 优化建议：
  • 在 NOI 比赛中，处理 $10^5$ 规模的读入，建议使用 std::ios::sync_with_stdio(false); 来优化 cin 的速度。
  • 字符映射：cnt[S[R] - 'A'] 是处理大写字母的标准姿势。

---

六、 总结：读题时的关键词

在竞赛中，如果你看到以下关键词，基本可以锁定本题型：

1. “最长子串...”：通常暗示滑动窗口或二分搜索。
2. “最多执行 K 次操作”：经典的滑动窗口约束条件。
3. “更改为任意字符”：暗示我们可以通过统计频次，利用“贪心”策略保留出现最多的字符。
4. “连续/重复”：考察区间内元素的统计特征。

教练点评： 这道题的难点在于 “maxCount 是否需要随左指针收缩而更新”。理解了“窗口只增不减”的技巧，能让你在处理更高难度的滑动窗口题目（如区间中值、区间众数限制）时，具备更敏锐的直觉。加油！