难度: Medium
给你一个字符串 s 和一个整数 k 。你可以选择字符串中的任一字符，并将其更改为任何其他大写英文字符。该操作最多可执行 k 次。
在执行上述操作后，返回 包含相同字母的最长子字符串的长度。
示例 1：
输入：s = "ABAB", k = 2 输出：4 解释：用两个'A'替换为两个'B',反之亦然。
示例 2：
输入：s = "AABABBA", k = 1 输出：4 解释： 将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。 子串 "BBBB" 有最长重复字母, 答案为 4。 可能存在其他的方法来得到同样的结果。
提示：
1 <= s.length <= 105s 仅由大写英文字母组成0 <= k <= s.length运行时间: 51 ms
内存: 16.0 MB
class Solution:
def characterReplacement(self, s: str, k: int) -> int:
l,max_str,count=0,0,defaultdict(int)
for r,c in enumerate(s):
count[c]+=1
if count[c]>max_str:
max_str=count[c]
if r-l+1-max_str>k:
count[s[l]]-=1
l+=1
return r-l+1
这个题解采用了滑动窗口的方法。首先定义两个指针l和r表示窗口的左右边界，并使用一个哈希表count来记录窗口内各字符的出现次数。变量max_str用来记录窗口中出现次数最多的字符的数量。在遍历字符串s的过程中，不断扩大窗口（右移r），并更新count和max_str。当窗口大小减去max_str的结果大于k时，说明窗口内无法通过k次替换达到全部相同的字符，此时需要左移l并相应地调整count。遍历结束后，窗口的大小即为结果。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def characterReplacement(self, s: str, k: int) -> int:
l, max_str, count = 0, 0, defaultdict(int) # 初始化左指针l，最大频率max_str，字符计数器count
for r, c in enumerate(s): # 遍历字符串s
count[c] += 1 # 增加当前字符的计数
if count[c] > max_str:
max_str = count[c] # 更新窗口中最多的字符的频率
if r - l + 1 - max_str > k: # 如果当前窗口的长度减去最多字符的数量大于k
count[s[l]] -= 1 # 减少窗口左端字符的计数
l += 1 # 移动左指针
return r - l + 1 # 返回最大窗口长度
滑动窗口方法适用于需要在字符串或数组中寻找满足特定条件的最长或最短子串或子数组的问题。在这个问题中，我们需要找到可以通过最多k次替换操作转换为单一字符的最长子串。滑动窗口允许我们在遍历字符串的同时动态调整子串的起止位置，有效地控制在k次替换内尽可能扩大子串长度。这种方法避免了不必要的重复计算，使得算法效率更高。
在这个算法中，`max_str`的更新只考虑当前右指针`r`指向的字符。每次将字符`c`加入窗口时，我们更新这个字符的计数，并检查是否需要更新`max_str`。这是因为每次只有一个新字符加入窗口，所以我们只需判断这个新增字符的计数是否超过了之前的`max_str`。这种方法避免了每次都遍历整个窗口重新计算所有字符频率，提高了算法的效率。
在当前算法实现中，当左指针`l`移动，即移除窗口左侧的字符时，我们减少该字符的计数。然而，我们不立即更新`max_str`，因为这将要求重新检查整个窗口的字符频率，这可能导致效率下降。在大多数情况下，`max_str`会略微过估计真实的最大频率，但这不会影响结果的正确性，因为窗口大小减去过估计的`max_str`大于k的情况下，真实的`max_str`也一定无法满足条件。这是一种以空间换时间的策略，保持算法的高效性。
这个条件基于这样的逻辑：如果当前窗口长度减去窗口内出现次数最多的字符的数量大于k，那么即使使用所有k次替换，也无法将窗口内其他字符全部替换为出现最多的字符。因此，这时需要移动左指针来尝试找到一个新的、可能更小的窗口，在这个新窗口中，通过最多k次替换可以满足所有字符相同的条件。这是一种通过调整窗口大小来试图找到满足条件的最长子串的方式。