# 替换后的最长重复字符（424）

# 题目

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

# 注意

字符串长度 和 k 不会超过 10^4。

# 示例

输入：s = "ABAB", k = 2 输出：4

解释：用两个'A'替换为两个'B',反之亦然。

输入：s = "AABABBA", k = 1 输出：4

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

# 算法

# 双指针

指针i指向重复字符字符串的开头，使用变量diff保存现在剩余可以替换字符的次数，变量curCount保存现在重复字符字符串的长度，变量maxCount保存当前最大的重复字符字符串的长度，指针j指向重复字符串的结尾

我们确定左指针i之后，向右移动右指针j，遇到不同的字符需要转换时我们将diff--，当右指针遍历到原字符串结尾时停止；或者当diff===0且s[j]!==s[i]（即没有转换字符串的次数且当前字符串结尾的字符需要转换）时停止，如果停止时我们还有剩余的diff次数，那么我们可以将当前字符串前面的字符再转换，即字符串长度=当前字符串长度+diff

最后我们返回结果maxCount，如果maxCount>s.length，我们则返回s.length

export const characterReplacement = (s, k) => {
	let maxCount = 0;
	for (let i = 0; i < s.length; i++) {
		let diff = k;
		let j = i;
		let curCount = 0;
		while (j < s.length) {
			if (diff <= 0 && s[i] !== s[j]) break;
			if (s[j] !== s[i]) diff--;
			curCount++;
			j++;
		}
		if (diff !== 0) curCount += diff;
		maxCount = Math.max(maxCount, curCount);
	}
	return maxCount < s.length ? maxCount : s.length;
};

# 滑动窗口

使用指针left和right维护一个滑动窗口，使用数组charCount来保存当前窗口内所有字符出现的次数，使用变量maxCount来保存当前窗口内出现次数最多字母的出现次数

每一轮循环开始时，我们将右指针right指向的字符在charCount中+1其出现次数，然后判断maxCount是否变化。

如果窗口内字符数量(right-left+1)减去窗口内出现次数最多的字符的出现次数maxCount，如果这个值不大于k，说明窗口满足替换条件，右指针right++；否则左指针left和右指针right同时右移且更新charCount...直到右指针指向s末尾

因为这里窗口只可能变大不可能缩小，所以最后的right-left的值就是整个过程中滑动窗口的最大值

export const characterReplacement = (s, k) => {
	let left = 0,
		right = 0;
	const charCount = new Array(26).fill(0);
	let maxCount = 0;
	while (right < s.length) {
		charCount[s[right].charCodeAt() - 65]++;
		maxCount = Math.max(maxCount, charCount[s[right].charCodeAt() - 65]);
		if (right - left + 1 - maxCount > k) {
			charCount[s[left].charCodeAt() - 65]--;
			left++;
		}
		right++;
	}
	return right - left;
};