【经典专题】爬行的毛毛虫——简单的滑动窗口模板

经典例题

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

输入：s = “AABABA”, k = 1
输出：4
解释：将中间的一个’B’替换为’A’,字符串变为 “AAAABA”。

滑窗模板

public int SlidingWindow(String s) {
	len = s.length();			// 串的长度
	int[] count = new int[N];	// 用于统计区间内的信息
	int L = 0, R = 0;			// 窗口边界，这是一个闭区间[L, R]
	int res = 0;				// 窗口最大宽度(最终结果)
	while (R < len) {
		count[s.charAt(R)]++;			// 修改统计值，因为R的移动改变了窗口
		while (区间不符合题意) {
			count[s.charAt(L)]--;		// 修改统计值，因为L的移动改变了窗口
			L++;						// 左指针被动移动（虫子的尾部）
		}
		res = Math.max(res, R - L + 1);		// 尝试更新res
		R++;								// 右指针主动移动（虫子的头部）
	}
}

模板说明

这篇文章的作者（here）提出了一个比滑动窗口更加生动形象的名字，虫取法。像一只蠕动前行的毛毛虫，后脚不动前脚向前方伸去，前脚不动后脚被拖拽跟上。
因此模板的核心思想就是：以右指针为驱动，拖着左指针向前走——右指针主动移动，探索新的区域；左指针被迫跟进，负责保证区间符合题意。
右指针的移动是一个固定的动作，每次固定移动一步，因此在内层的那个while之外；左指针的移动是一个被迫的动作，每次移动的步数并不确定，因此在内层的那个while之中。

一些理解

这里题目中，给出的可能是字符串/数组，将字符串转化为数组（toCharArray）会得到不小的性能优化哦
滑窗的本质是一个合法区间，既然是区间，就涉及到了所谓双指针。其实，“双指针”这个说法过于宽泛，一般而言的双指针，通常是两个(甚至三个、四个)指针从整体的两侧边界向内收缩，可以认为两个指针的方向是「相向而行」；而滑动窗口，区间不倾向于收缩而是倾向于移动，可以认为两个指针的方向是「同向而行」

本题答案

>>> 1.count数组统计的是区间内每个字母出现的次数，并维护了出现次数最多的字母的出现次数maxCnt
>>> 2.关于区间的合法性，用了一个巧妙的判断：maxCnt + k < R - L + 1(🌟🌟🌟)
>>> 2.即(出现次数最多的字母的出现次数+容错次数即可替换次数k)都无法填满这个窗口(R-L+1)的话，则非法了

>>> 3.还有一个小细节可能需要理解，就是内层while可以写成if
>>> 3.这是因为在本题中，可以保证由于R走了一步而导致到非法，L走一步就一定能纠正回来———天机在于maxCnt此时并未维护，while循环仅仅会执行一次

class Solution {
    public int characterReplacement(String s, int k) {
        int len = s.length();
		char[] charArr = s.toCharArray();
        int[] count = new int[26];
        int maxCnt = 0;

        int L = 0, R = 0;
        int res = 0;
        while (R < len) {
            count[charArr[R] - 'A']++;
            maxCnt = Math.max(maxCnt, count[charArr[R] - 'A']);
            while (maxCnt + k < R - L + 1) {
                count[charArr[L] - 'A']--;
                L++;
            }
            res = Math.max(res, R - L + 1);
            R++;
        }
        return res;
    }
}