https://leetcode.com/problems/longest-repeating-character-replacement/
滑动窗口的典型，还是有一些trick的

个人解答

  1. class Solution:
  2.     def characterReplacement(self, s: str, k: int) -> int:
  3.         c = collections.Counter()
  4.         maxCnt = 0
  5.         res = 0
  6.         l, r = 0, 0
  7.         while r < len(s):
  8.             c[s[r]] += 1
  9.             maxCnt = max(maxCnt, c[s[r]])
  10.             while r - l + 1 > k + maxCnt:
  11.                 c[s[l]] -= 1
  12.                 l += 1
  13.             res = max(res, r - l + 1)
  14.             r += 1
  15.         return res

题目分析

比较容易能够想到一个基础的解法：
题目限定了字符是大写字母，也就26个嘛，对每一个都找可替换的最长子串，这个可以用sliding window解决，整体的思路还是比较直观的，直接看代码：

  1. class Solution:
  2.     def characterReplacement(self, s: str, k: int) -> int:
  3.         def f(x):
  4.             l, r, cnt = 0, 0, 0
  5.             res = 0
  6.             while r < len(s):
  7.                 if s[r] == x:
  8.                     cnt += 1
  9.                 while r - l + 1 > k + cnt:
  10.                     if s[l] == x:
  11.                         cnt -= 1
  12.                     l += 1
  13.                 res = max(res, r - l + 1)
  14.                 r += 1
  15.             return res
  16.         res = 0
  17.         for x in string.ascii_uppercase:
  18.             res = max(res, f(x))
  19.         return res

但是，本题目其实有更优雅更高效的处理方式，对每个字母做sliding window做了很多无用功，可以同时进行。
对于一个(l, r)的区间，我们并不关注到底是哪个字母出现最多，只关注出现最多的数量，因此，只要维护当前区间，每个字母的数量，并时刻取最大的数量就可以了。
有且只有保证区间的长度，没有超过区间内最大字母个数+可替换个数，这个区间一定是合法的，找出最长的合法区间即可。