题目描述：
给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。
注意：字符串长度 和 k 不会超过 10^4。
示例 1：
输入：s = "ABAB", k = 2
输出：4
解释：用两个'A'替换为两个'B',反之亦然。
示例 2：
输入：s = "AABABBA", k = 1
输出：4
解释：
将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
子串 "BBBB" 有最长重复字母, 答案为 4
思路分析：
一看到最长字符串就想到滑动窗口。
算法流程：
- 右边界先移动找到一个满足题意的可以替换 k 个字符以后，所有字符都变成一样的当前看来最长的子串，直到右边界纳入一个字符以后，不能满足的时候停下；
- 然后考虑左边界向右移动，左边界只须要向右移动一格以后，右边界就又可以开始向右移动了，继续尝试找到更长的目标子串；
- 替换后的最长重复子串就产生在右边界、左边界交替向右移动的过程中。
class Solution: def characterReplacement(self, s: str, k: int) -> int: from collections import defaultdict d = defaultdict(int) l = 0 maxn = 0 for r in range(len(s)): d[s[r]] += 1 maxn = max(maxn, d[s[r]]) if r - l + 1 > maxn + k: # bc it is for loop, r += 1 is later than if clause d[s[l]] -= 1 l += 1 return len(s) - l
class Solution { public int characterReplacement(String s, int k) { int len=s.length(); if(len<2){ return len; } char[] chararray=s.toCharArray(); int left=0,right=0; int maxCount=0,res=0; int[] freq = new int[26]; while(right<len){ freq[chararray[right]-'A']++; maxCount=Math.max(maxCount,freq[chararray[right]-'A']); right++; if(right-left>maxCount+k){ freq[chararray[left]-'A']--; left++; } res=Math.max(res,right-left); } return res; } }
复杂度分析：
时间复杂度：O(N)，这里 N 是输入字符串 S 的长度；
空间复杂度：O(A)，这里 A 是输入字符串 S 出现的字符 ASCII 值的范围。
