LeetCode 424. 替换后的最长重复字符(滑动窗口)（双指针）
LeetCode 424. 替换后的最长重复字符(滑动窗口)（双指针）
题目
给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。
注意：字符串长度 和 k 不会超过 104。
示例 1：
输入：s = "ABAB", k = 2 输出：4 解释：用两个'A'替换为两个'B',反之亦然。 示例 2：
输入：s = "AABABBA", k = 1 输出：4 解释： 将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。 子串 "BBBB" 有最长重复字母, 答案为 4。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/longest-repeating-character-replacement 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
本体采用滑动窗口思想，从某个字符开始，如果后面的字符和开始字符一样则这个字符串长度++，若不一样分两种情况， 1.这个字符串中不一样字符的个数小于k，则让k--，长度++。 2.这个字符串中不一样的字符个数大于等于k，那么记录的长度就是此字符串的长度。然后继续下一个字符串，下一个字符串开始的位置应该为上一个字符串第一次不一样字符的位置。
根据上面思路可以确定几个变量
n 记录第一次不一样元素指针位置
m 某字符串长度
p 记录k
t 记录某字符串开始字符
jud 判断是否记录(记录第一个不一样字符的时候判断条件应该为if (s[i] != s[t])就是当前字符和开始字符不一样，但是如果k > 1，那么后面还会有别的字符和开始字符不一样，但是不是第一个不一样的字符，所以就要用jud加一个判断)
此题有几个坑： 比如字符串"ABBBA",k = 2。按照上面的思路得出结果是4，但答案是5,因为从B开始记录到最后最多只有4个元素，但是支教换了一个A，而k = 2，所以第一个A也是可以交换的，所以就要在最后一个字符串加一个判断： 如果p还有剩余(此字符串已经交换的元素小于k)，并且t > 0(此字符串开始位置不为0，如果为0前面也没有字符可以交换)，则此字符串长度 + min(t, p)
class Solution {
public:
int characterReplacement(string s, int k) {
if (s.size() == 0) {
return 0;
}
int n = 0; //记录第一次不一样元素指针位置
int m = 1; //某字符串长度
int p = k; //复制k
int num = 1; //最长
int t = 0; //记录某字符串开始字符
bool jud = false; //判断是否记录
for (int i = 1; i < s.size(); i++) {
if (s[i] == s[t]) {
m++;
}
else {
if (jud == false) {
n = i;
jud = true;
}
if (p <= 0) {
i = n;
t = n;
jud = false;
if (m > num) {
num = m;
}
p = k;
m = 1;
}
else {
m++;
p--;
}
}
}
if (m >= num) {
num = m;
if (t > 0 && p > 0) {
num += min(t, p);
}
}
return num;
}
};
腾讯云开发者
