Vasya 与字符串 题解

算法说明

最终的最长相同字符子串只可能全部为 a 或全部为 b。分别计算把某个连续子串变成全 a、全 b 时能够取得的最大长度，再取两者的最大值。

对于固定的目标字符 target，使用双指针维护窗口 $[left,right]$，并记录窗口中不等于 target 的字符数 changed：

1. 将 s[right] 加入窗口；若它不等于 target，则 changed 加一。
2. 当 changed>k 时，不断右移 left；移出的字符不等于 target 时，changed 减一。
3. 此时窗口至多需要修改 $k$ 个字符，用窗口长度更新答案。

正确性证明

先固定目标字符 target。

算法在每次更新答案前都保证窗口内不等于 target 的字符数不超过 $k$，所以将这些字符修改为 target 后，整个窗口均为 target。因此算法记录的每个长度都是合法的。

对于任意右端点 $right$，如果加入新字符后窗口需要修改的字符数超过 $k$，算法会一直右移左端点，直到窗口重新合法。停止时的 $left$ 是使窗口合法的最小左端点：更靠左的窗口包含更多字符，且在停止前仍有超过 $k$ 个非目标字符。因此，算法取得了以 $right$ 为右端点、能够变成全 target 的最长合法窗口。

枚举所有右端点后，算法便求出了能够变成全 target 的最长连续子串。题目中相同字符子串的字符只能是 a 或 b，分别以二者为目标计算并取最大值，就得到全局最优答案。

复杂度分析

对每个目标字符，左右指针都只会单调移动至多 $n$ 次，时间复杂度为 $O(n)$。只使用常数个变量，额外空间复杂度为 $O(1)$。

边界与易错点

• $k=0$ 时不能修改任何字符，答案是原串最长连续相同段。
• $k=n$ 时可以把整个字符串改成同一个字符，答案为 $n$。
• 必须同时计算变成全 a 和全 b 的情况。
• 窗口中非目标字符数恰好等于 $k$ 时仍然合法；只有大于 $k$ 才收缩。
• 收缩窗口时，只有移出的字符不是目标字符，才减少 changed。

参考代码

#include <iostream>
#include <string>
using namespace std;

int longest(const string &s, int k, char target) {
    int left = 0;
    int changed = 0;
    int answer = 0;
    for (int right = 0; right < static_cast<int>(s.size()); ++right) {
        if (s[right] != target) ++changed;
        while (changed > k) {
            if (s[left] != target) --changed;
            ++left;
        }
        int length = right - left + 1;
        if (length > answer) answer = length;
    }
    return answer;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, k;
    string s;
    if (!(cin >> n >> k >> s)) return 0;
    int answer_a = longest(s, k, 'a');
    int answer_b = longest(s, k, 'b');
    cout << (answer_a > answer_b ? answer_a : answer_b) << '\n';
    return 0;
}