一、问题描述
给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换k次。在执行上述操作后，找到包含重复字母的最长子串的长度。
注意:
字符串长度 和 k 不会超过。
示例 1:
输入:s = "ABAB", k = 2输出:4解释:用两个'A'替换为两个'B',反之亦然。
示例 2:
输入:s = "AABABBA", k = 1输出:4解释:将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。子串 "BBBB" 有最长重复字母, 答案为 4。
题目来源：LeetCode 链接：https://leetcode-/problems/longest-repeating-character-replacement
二、解题思路
1.暴力法，一般时间都会超限
class Solution {public:int characterReplacement(string s, int k) {int k2=k, maxlen=0, first=s.length();int i=0, j=0; //一个左边界i，一个右边界jwhile(i<s.length()&&j<s.length()){if(s[j]!=s[i]){if(k2>0){k2--;first = first< j ? first: j; //first记录第一个跟s[i]不相同的元素下标//后面可以直接把i重新赋值为first，而不是i+1j++;}else //如果k次修改机会用完{int temp = j-i;maxlen = maxlen<temp?temp:maxlen; //记录最长字符串长度if((s.length()-first)>maxlen) //只有first后面的字符串大于目前的maxlen{ //继续执行才有意义，否则直接breaki = first; //把i赋值为firstj = i+1;//j为i+1k2 = k; //k2复原为原值}elsebreak;}}else{j++;}int temp = j-i;maxlen = maxlen<temp?temp:maxlen;}return maxlen;}};
2.滑动窗口法
上面的暴力法最坏情况了的时间复杂度其实可以达到, 这是因为当k次修改机会用完又遇到跟左边界值s[i]不同的元素时，采取的策略是往回走，把i赋值为first，j赋值为i+1。而滑动窗口的思想就是一直往前滑，争取达到O(n)的时间复杂度。而这要怎么才能做到？
该方法时记录滑动窗口内的最多个数的字符即charMax，只要满足right - left + 1 > charMax + k即可继续向右扩张，即right++，不满足的时候就窗口整体向右移动，即同时right++，left++。这时候，假设后面都没有更长的替换后连续字符串的话，那么这个窗口长度会一直不变，知道循环结束（right走到终点），而如果后面还有更长的替换后连续字符串的话，这个窗口就会再次扩张。最后返回窗口大小，就是所求的替换后最长连续字符串的长度。
class Solution {public:int characterReplacement(string s, int k) {if(s.length()==0)return 0;int map[26]={0}; //map用来记录字符数int i=0, charmax=0;//map数组下标为键，内容为值for(int j=0;j<s.length();j++){int index = s[j]-'A';map[index]++; //向右扩张一步charmax=charmax>map[index]?charmax:map[index];//更新charmaxif((j-i+1)>charmax+k){map[s[i]-'A']--; //如果不符合条件，左边收缩//保持窗口长度不变i++;}}return s.length()-i;}};
三、总结
1.滑动窗口通常由扩张、收缩、移动三种行为，根据解题过程的不同阶段采取不同的行为
2.滑动窗口经常搭配map使用 ，意在记录滑动窗口中的信息
3.滑动窗口很适合解决字符串类的题目
滑动窗口：给你一个仅由大写英文字母组成的字符串 你可以将任意位置上的字符替换成另外的字符 总共可最多替换k次。在执行上述操作后 找到包含重复字母的最长子串的长度。
