【leetcode】替换后的最长重复字符(滑动窗口)

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

注意:
字符串长度 和 k 不会超过 104。

示例 1:

输入:
s = “ABAB”, k = 2

输出:
4

解释:
用两个’A’替换为两个’B’,反之亦然。
示例 2:

输入:
s = “AABABBA”, k = 1

输出:
4

解释:
将中间的一个’A’替换为’B’,字符串变为 “AABBBBA”。
子串 “BBBB” 有最长重复字母, 答案为 4。

链接：https://leetcode-cn.com/problems/longest-repeating-character-replacement

思路分析：

一开始想的动态规划，结果越想越觉得不对劲。看了题解才发现是滑动窗口。
**滑动窗口就是要找区间的满足条件。**若 [l,r] 区间里的数都满足条件，则r++直至区间里的数不满足条件。随后 l++ 直至区间又满足条件。就这样一直往前推直到 r >= n停止。关键就是要找区间的满足条件。

这道题的区间满足条件是：记区间里出现重复字母最多的次数为maxcnt，当r-l+1 - maxcnt <= k 时区间满足条件。

为什么是这样呢？因为**区间 [l,r] 长度减去maxcnt的含义就是与出现最多的那个字符不相同的个数，即需要替换的字符个数。**若需要替换的字符个数 <= k，区间满足条件，r++; 其 > k，区间不满足条件，l++;

这样代码就好写了。哈希表解决maxcnt，然后按照滑动窗口推下去即可。
下面上代码：

class Solution {
public:
    int characterReplacement(string s, int k) {
        int l = 0, r = 0, n = s.length(), maxcnt = 0, ans = 0;
        map<char,int> mp;
        while(r < n)
        {
            mp[s[r]]++;
            maxcnt = max(maxcnt,mp[s[r]]);
            while(r-l+1 - maxcnt > k)
            {
                mp[s[l]]--;
                l++;
            }
            ans = max(ans,r-l+1);
            r++;
        }
        return ans;
    }
};