这是“替换后的最长重复字符”问题的标准题解。在 NOI 竞赛中，这道题考察的是滑动窗口的单调性维护以及贪心策略的巧妙运用。

一、 题解标准代码 (C++14)

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

/**
 * 核心逻辑：
 * 我们寻找一个最长的窗口 [left, right]，使得：
 * (窗口长度 - 窗口内出现次数最多的字符频率) <= k
 * 
 * 关键点：max_cnt 并不需要随着窗口左移而减小。
 * 因为我们追求的是“最长”，只有当出现一个比历史 max_cnt 更大的频率时，
 * 才可能产生一个更长且合法的窗口。
 */

int main() {
    // 竞赛优化：加速输入输出
    ios::sync_with_stdio(false);
    cin.tie(0);

    string s;
    int k;
    
    // 注意：某些比赛题目输入顺序可能不同，需仔细读题
    if (!(cin >> s >> k)) return 0;

    int n = s.length();
    vector<int> cnt(26, 0); // 频次统计数组
    int left = 0, right = 0;
    int max_cnt = 0; // 窗口内历史上出现过的最高字符频率

    // 右指针不断向右移动
    for (right = 0; right < n; ++right) {
        // 1. 进窗：更新当前字符频次并维护历史最高频次
        int cur_char = s[right] - 'A';
        cnt[cur_char]++;
        max_cnt = max(max_cnt, cnt[cur_char]);

        // 2. 判定：当前窗口是否非法？
        // 易错点：窗口长度为 (right - left + 1)
        // 逻辑：如果(非众数)字符的数量 > k，说明当前窗口无法通过 k 次修改变全同
        if (right - left + 1 - max_cnt > k) {
            // 3. 平移：此时不需要大幅缩小窗口，只需将整个窗口向右平移一格
            // 因为我们只需寻找“更长”的，当前大小已经不合法了，没必要保留
            cnt[s[left] - 'A']--;
            left++;
        }
        
        // 关键点：这里的窗口长度并不一定在每一时刻都合法，
        // 但它在整个过程中维持了“历史上出现过的最大合法长度”。
    }

    // 最终答案：窗口的最终宽度 (right此时等于n)
    cout << right - left << endl;

    return 0;
}

二、 时间与空间复杂度分析

1. 时间复杂度分析

• 指针移动：右指针 right 严格遍历一次字符串，移动 $n$ 次。左指针 left 最多移动 $n$ 次。
• 计算开销：每次移动只涉及一次数组下标访问和一次 max 比较，时间为 $O(1)$。
• 总结：总时间复杂度为 $O(n)$。
  • 在 $n = 10^5$ 的数据规模下，运算量约 $2 \times 10^5$ 次，耗时通常在 10ms 以内，远优于 1 秒的限时。

2. 空间复杂度分析

• 存储空间：使用 vector<int> cnt(26) 存储 26 个大写字母的频次，空间为 $O(26)$。
• 输入开销：存储字符串 $s$ 占用 $O(n)$。
• 总结：除输入外，辅助空间复杂度为 $O(1)$。在 128MB 内存限制下极其安全。

三、 时间复杂度优化建议

本算法已达到理论最优的线性复杂度。在 NOI 实际赛场上，可以注意以下微小优化：

1. 非收缩窗口技巧：
   • 正如代码中所示，我们使用 if 而不是 while。这不仅简化了逻辑，还减少了频繁更新 max_cnt 的次数（因为 max_cnt 只需要单调递增）。
2. 快读（Fast I/O）：
   • 若字符串长度达到 $10^6$ 或更高，std::cin 即使加了 ios::sync_with_stdio(false) 也可能比 fread 慢。但在 $10^5$ 规模下，当前的优化已足够。
3. 避免重复计算 s.length()：
   • 在 for 循环条件中直接使用提前存好的变量 n，避免每一轮循环都调用函数。

四、 总结：读题时的关键点（填坑指南）

1. “连续子串”还是“子序列”？
   • 题目明确要求“子串”（Substring），这是滑动窗口的通行证。如果是子序列（Subsequence），则通常需要动态规划或贪心。
2. $max\_cnt$ 的理解陷阱：
   • 这是本题最精妙的地方。很多选手会在这里写一个 while 循环并试图在 $L$ 右移时重新扫描 cnt 数组来更新 $max\_cnt$。虽然 $26 \times N$ 的复杂度也能过，但理解了 “历史最大窗口” 的概念后，代码会更加健壮。
3. 边界值测试：
   • 当 $K=0$ 时：算法退化为寻找原始字符串中最长的重复字符子串。
   • 当 $K \ge N$ 时：算法应该正确返回 $N$。
4. 字符集规模：
   • 如果题目改为包含小写字母或数字，cnt 数组的大小要相应调整为 128 或更多。

教练点评： 在 NOI 普及组中，滑动窗口是必考点。这道题的精髓在于“用 O(1) 的维护成本去监控区间的复杂属性”。记住：窗口不一定要时刻保持完美合法，它有时更像是一个“捕兽夹”，在滑动的过程中锁定了曾经遇到的最大猎物。加油！

在 NOI 竞赛中，构造高质量的数据点需要覆盖：极小规模、无修改（K=0）、全修改（K=N）、全等字符、全异字符、以及最大规模随机数据。

由于本题是 $O(N)$ 线性算法，生成器运行速度极快。以下是为你准备的数据生成器 C++ 代码。

一、 数据生成器 (C++14)

该生成器会自动创建 1.in ~ 10.in 和对应的 1.out ~ 10.out 文件。

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
#include <random>
#include <chrono>

using namespace std;

// --- 标程 (Standard Solution) 用于生成 .out 文件 ---
int get_ans(string s, int k) {
    int n = s.length();
    if (n == 0) return 0;
    int cnt[26] = {0};
    int left = 0, max_cnt = 0, res = 0;
    for (int right = 0; right < n; ++right) {
        max_cnt = max(max_cnt, ++cnt[s[right] - 'A']);
        if (right - left + 1 - max_cnt > k) {
            cnt[s[left] - 'A']--;
            left++;
        }
        res = max(res, right - left + 1);
    }
    return res;
}

// --- 随机字符串生成工具 ---
// 注意这里的参数是 mt19937 &rng，传递的是引擎引用
string make_string(int n, int alpha_range, mt19937 &rng) {
    string s = "";
    uniform_int_distribution<int> dist(0, alpha_range - 1);
    for (int i = 0; i < n; ++i) {
        s += (char)('A' + dist(rng));
    }
    return s;
}

// --- 生成测试点数据 ---
void generate(int test_idx, int n, int k, string s) {
    string in_file = to_string(test_idx) + ".in";
    string out_file = to_string(test_idx) + ".out";
    
    ofstream fin(in_file);
    fin << s << "\n" << k << endl;
    fin.close();
    
    ofstream fout(out_file);
    fout << get_ans(s, k) << endl;
    fout.close();
    
    cout << "Generated case " << test_idx << ": n=" << n << " k=" << k << endl;
}

int main() {
    // 随机数种子
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

    // 1. 最小规模边界
    generate(1, 1, 0, "A");

    // 2. K = 0 (不允许修改)
    generate(2, 10, 0, "AABBCDDDEE");

    // 3. K 远大于长度 (全覆盖)
    generate(3, 10, 20, "ABCDEFGHIJ");

    // 4. 全相同字符
    generate(4, 5000, 100, string(5000, 'Z'));

    // 5. 交替重复模式
    string s5 = "";
    for(int i=0; i<5000; ++i) s5 += (i % 2 == 0 ? 'A' : 'B');
    generate(5, 5000, 100, s5);

    // 【修正点】：这里传 rng 而不是 rng()
    // 6. 较大规模随机 (字符集小 A-B)
    generate(6, 100000, 100, make_string(100000, 2, rng));

    // 7. 较大规模随机 (字符集大 A-Z)
    generate(7, 100000, 500, make_string(100000, 26, rng));

    // 8. K 极小 (只能改 1 个)
    generate(8, 100000, 1, make_string(100000, 5, rng));

    // 9. 构造长段连接点
    string s9 = string(40000, 'A') + string(200, 'B') + string(59800, 'A');
    generate(9, 100000, 201, s9);

    // 10. 最大规模纯随机
    generate(10, 100000, 50000, make_string(100000, 26, rng));

    cout << "\nAll data generated successfully." << endl;
    return 0;
}

二、 测试点规划说明 (OJ 参考)

三、 生成器编写与优化提示

1. 非递归标程：
   • 生成器内部集成的 get_ans 采用了迭代式滑动窗口，时间复杂度为 $O(N)$，空间复杂度 $O(1)$（计数数组为 26）。这保证了即使在生成 $N=10^5$ 的数据时，也不会发生栈溢出（Stack Overflow），且运行速度极快。
2. 数据合法性：
   • 字符串严格限制在大写字母 'A'-'Z'。
   • $K$ 的生成涵盖了从 0 到 $N+K$ 的范围，符合题目要求的各种极端输入。
3. IO 性能：
   • 在处理 $10^5$ 规模的读写时，虽然 C++ 的 ofstream 默认效率尚可，但生成大量数据点时建议使用 \n 代替 endl 以避免频繁刷新缓冲区。
4. 随机数建议：
   • 使用了 C++11 的 std::mt19937 引擎。在 NOI 竞赛中，如果编译器版本较老（如 C++98），应替换为传统的 srand(time(0)) 和 rand()。但在 C++14 环境下，mt19937 能提供更高质量的均匀分布。

教练点评： 这套数据不仅能测出代码的正确性，更能测出选手是否误用了 $O(N \cdot \Sigma)$ 或 $O(N^2)$ 的算法（如每次移动窗口都暴力遍历 26 个字母寻找 max_cnt）。在第 6-10 点的大规模压力下，不合格的常数优化将无所遁形。加油！