双指针滑动窗口

原题地址（中等）

方法1—双指针/滑动窗口

思路

这题好TM难啊。。
还是看了两个官方题解

代码最难理解的地方就是maxn不是实时维护的，这点可以看wiewei哥的题解，也就是官方题解第一个
image.png

通常的滑动窗口要求窗口性质的保持作为循环不变量，这道题用if不用while感觉还是很巧妙的； 尽管每次循环时窗口不一定满足窗口定义，但循环中窗口状态在状态空间的轨迹一定会经过目标状态。

代码

  1. class Solution:
  2.     def characterReplacement(self, s: str, k: int) -> int:
  3.         num = [0] * 26
  4.         n = len(s)
  5.         maxn = left = right = 0
  7.         while right < n:
  8.             num[ord(s[right]) - ord("A")] += 1
  9.             maxn = max(maxn, num[ord(s[right]) - ord("A")])
  10.             if right - left + 1 - maxn > k:
  11.                 num[ord(s[left]) - ord("A")] -= 1
  12.                 left += 1
  13.             right += 1
  15.         return right - left

时空复杂度

时间复杂度：O(n)，其中 nn 是字符串的长度。我们至多只需要遍历该字符串一次。

空间复杂度：O(∣Σ∣)，其中∣Σ∣ 是字符集的大小。我们需要存储每个大写英文字母的出现次数。