LeetCode 424 替换后的最长重复字符

题目链接

给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。

注意：字符串长度 和 k 不会超过 1e4。

示例 1：

输入：s = "ABAB", k = 2
输出：4
解释：用两个'A'替换为两个'B',反之亦然。

示例 2：

输入：s = "AABABBA", k = 1
输出：4
解释：
将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
子串 "BBBB" 有最长重复字母, 答案为 4。

双指针，用 $l,r$ 两个指针寻找最大长度，先移动 $r$ 指针，并记录此时 $[l,r]$ 区间内某一字符出现最多的次数 $mx$，显然 $k$ 次替换最大的区间长度就是 $l+mx+k-1$，也即 $r<l+mx+k-1$，一旦 $r$ 指针超过此范围，将 $l$ 指针向右移动即可，整个思路就是先移动右指针，再移动左指针，寻找最大区间长度即可，AC代码如下:

class Solution {
public:
    int characterReplacement(string s, int k) {
        vector<int> num(26);
        int mx = 0, l = 0, r = 0, n = s.size();
        while (r < n) {
            num[s[r] - 'A']++;
            mx = max(mx, num[s[r] - 'A']);
            if (r - l + 1 - mx > k) {
                num[s[l] - 'A']--;
                l++;
            }
            r++;
        }
        return r - l;
    }
};