不定长滑动窗口

不定长滑动窗口，是指窗口长度不固定，会根据条件进行窗口收缩，即窗口的长度在变化，不会按照固定的长度推进。一般情况下，当窗口符合题意条件后，开始移动左边界进行窗口收缩，当不符合题意条件时，开始移动右边界进行窗口扩张。这类问题的核心是check函数的设计，找对check函数，基本上就能解开该类问题。

图示

模板

不定长类问题核心是check函数的设计，怎么找到符合窗口收缩的条件是关键。注意，这里的check函数只是一个概念，具体编码里也可能只是两个变量的比较。

function VariableLengthWindow(s, t) {
  let left = 0;
  let right = 0;
  let window = new Set(); //记录窗口内容
  
  // 不定长类问题的关键是check函数地设计，需要注意的是 check 函数只是一个概念，即：符合窗口收缩的条件
  const check = () => {
    // 判断是否符合窗口收缩的条件，比较 pattern 和 window
    // 一般用哈希表 或 数组，来作为窗口比较的载体，但是具体问题具体分析
  };

  while (right < s.length) {
    window.add(s[right]);

    // 判断是否符合窗口收缩条件，对窗口进行收缩
    while (check()) {
      window.delete(s[left]);
      left++;
    }

    // 记录符合条件的值，极大值或极小值等

    right++;
  }
  
  return xxx;
}

例题

不定长类问题的核心在于check函数设计，即窗口与模式要求的匹配，这类问题通常可以用哈希表（Map或Set）来做为数据结构的承载，但是一般说来，哈希表的性能不高，进阶用法是数组或变量。即基础用法通常考虑哈希表，进阶用法考虑数组或特定变量。请在下面的例子中仔细体会。

LC 76. 最小覆盖子串 (opens new window)

Q：

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
• 如果 s 中存在这样的子串，我们保证它是唯一的答案。

A：虽然这题为困难题，但难度其实是中等级别。这道题目用不定长的滑动窗口来解决，不断扩张窗口，当窗口内子串覆盖了t的所有字符，记录最小长度，并开始收缩窗口。最终最小长度和起始点就是答案。这里给出两种解法，哈希表版和数组版，哈希表版为基础版，一般类的问题都可由哈希表来解决，但是哈希表效率低点；数组版为进阶版本，效率较高。

哈希表版解法，哈希表为基础解法版，一般类的问题都可由哈希表来解决，但是哈希表效率低点

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function (s, t) {
  	
    const pattern = new Map();  // 用于记录t串的字符数
    const window = new Map();   // 用于记录窗口内的字符数

    let left = 0;
    let right = 0;
    let minL = Infinity;
    let start = 0;

    // 处理t串
    for (const char of t) {
        pattern.set(char, pattern.has(char) ? pattern.get(char) + 1 : 1);
    }

    // 设计check函数，比较 window 是否包含 pattern
    // 注意，符合题意要求的条件下，pattern 是 window的一个子集
    const check = () => {
        if (window.size < pattern.size) return false;

        // pattern 如果不是 window的一个子集，则说明window的字符串不包含t
        for (const [char, count] of pattern) {
            if (!window.has(char) || window.get(char) < count) return false;
        }

        return true;
    }

    while (right < s.length) {
        // 扩张窗口
        window.set(s[right], window.has(s[right]) ? window.get(s[right]) + 1 : 1);

        // 检查是否符合题意，即当前[left, right]区间子串是否包含t的全部字符。符合时进行记录处理，并开始收缩窗口
        while (check()) {

            // 符合题意时，记录当前子串长度和开始位置，寻找最小的长度
            // [left, right]
            const d = right - left + 1;
            if (d < minL) {
                minL = d;
                start = left;
            }

            // 收缩窗口，寻找最小子串
            {
                let count = window.get(s[left]) - 1;
                if (count == 0) {
                    window.delete(s[left]);
                } else {
                    window.set(s[left], count);
                }
                left++;
            }
        }

        right++;
    }

    return minL == Infinity ? "" : s.substring(start, start + minL);
};

数组版解法，数组版的效率比哈希表效率要高

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function (s, t) {
    // 由于s和t是由英文字符组成，即纯由ASCII表组成，则可用128数组标示
  	// 频数数组
    const pattern = new Array(128).fill(0);
    const window = new Array(128).fill(0);
    let distance = 0;   // 用于记录t串不同字符数
    let match = 0;  // 用于记录窗口内与 t串相同字符数 的个数

    let left = 0;
    let right = 0;
    let minL = Infinity;
    let start = 0;

    // 处理t串
    for (const char of t) {
        pattern[char.charCodeAt()]++;
    }
    // 这里处理完的 distance 表示t传内不同字符的个数
    for (const count of pattern) {
        if (count > 0) distance++;
    }

    while (right < s.length) {
        // 扩张窗口
        const rIndex = s[right].charCodeAt();
        window[rIndex]++;

        // match表示窗口内与t串相同字符的个数，这里需要仔细体会下
        if (window[rIndex] == pattern[rIndex]) {
            match++;
        }

        // 这里的 match == distance 即是check函数，check函数只是一个概念，具体形式多样
        while (match == distance) {
            let min = right - left + 1;
            if (min < minL) {
                minL = min;
                start = left;
            }

            // 收缩窗口
            const lIndex = s[left].charCodeAt();
            if (window[lIndex] == pattern[lIndex]) {
                match--;
            }
            window[lIndex]--;
            left++;
        }

        right++;
    }

    return minL == Infinity ? "" : s.substring(start, start + minL);
};

LC 424. 替换后的最长重复字符 (opens new window)

Q：

给你一个字符串 s 和一个整数 k 。你可以选择字符串中的任一字符，并将其更改为任何其他大写英文字符。该操作最多可执行 k 次。

在执行上述操作后，返回包含相同字母的最长子字符串的长度。

提示：

• 1 <= s.length <= 105
• s 仅由大写英文字母组成
• 0 <= k <= s.length

A：题目的核心是寻找出最大的字符数，因此可用频数数组来统计字符个数。一定要注意，check函数只是一个概念，具体形式是多样的，通过本题仔细体会下这点。

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var characterReplacement = function (s, k) {
  	// 由于全部为大写字母，因此最多26个字符
    const freq = new Array(26).fill(0);
    const ACode = "A".charCodeAt();

    let left = 0;
    let right = 0;
    let maxCount = 0;
  
    // 滑动窗口区间[left, right)
    while (right < s.length) {
        const rightIndex = s[right].charCodeAt() - ACode;
        freq[rightIndex]++;
      	// 这一行代码也可以放最下面，但是 if 判断内就要改为 right - left + 1 > maxCount + k，为了与最后 return 语句统一，放在这里写。
        right++;

        maxCount = Math.max(maxCount, freq[rightIndex]);
      
      	// 本题的check函数
        // maxCount + k 表示字符数最大的字符加上其他字符，已经不满足要求了（即此时的字符串替换k个字符串后，也不是一样的字符），说明left已不满足要求，需要移动left。另外需要注意，这里没有 修改 maxCount，因为题目要寻找的是最长子串，因此小于这个子串的都不符合题意，因此后面 maxCount 要么增大要么不变，如果后面没有比当前更长大字符串，则这个滑动窗口会保持 left - right区间一直移动到末尾，因此最后可以返回 right - left
        if (right - left > maxCount + k) {
            freq[s[left].charCodeAt() - ACode]--;
            left++;
        }
    }

    // 注意这里不能是 return maxCount + k，因为 maxCount + k >= right - left。考虑极端情况，s中所有的字符都相同，此时 maxCount = s.length
    return right - left;
};

LC 3. 无重复字符的最长子串 (opens new window)

Q：

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

A：这是一道标准的不定长滑动窗口题目，整体编码比较简单。这里给出两个解法，一个是标准的模板式代码，一个是优化版的代码，仔细体会下不同。

• 模板式代码，利用哈希集合记录字符，遇到重复字符后，收缩窗口

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
    // 滑动窗口，不定长
    const window = new Set();

    let left = 0;
    let right = 0;
    let maxL = 0;

    while (right < s.length) {

        // check函数设计
        // 由于可能已经包含了s[right]，因此这里放到最前面写
        while (window.has(s[right])) {
            window.delete(s[left]);
            left++;
        }

        // 扩大窗口
        window.add(s[right]);

        // 计算最大值
        maxL = Math.max(maxL, right - left + 1);

        right++;
    }

    return maxL;
};

• 优化后代码，利用哈希Map记录字符及其对应索引，遇到字符后直接移动左指针到重复字符索引的下一位，避免一位一位的移动，提高了效率。

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
    const window = new Map();
    let left = 0;
    let right = 0;
    let maxL = 0;
    while (right < s.length) {
        // 快速移动left，如果已经包含了s[right]字符，则left可直接移动到s[right]的下一位
        if (window.has(s[right])) {
            // 需要注意的是，这里的 window 并不是真正的窗口，我们没有对超出该[left,right]的做移除操作，因此需要比较left
            left = Math.max(left, window.get(s[right]) + 1);
        }
        window.set(s[right], right);

        // 记录最大值
        maxL = Math.max(maxL, right - left + 1);

        right++;
    }
    return maxL;
};

LC 438. 找到字符串中所有字母异位词 (opens new window)

Q：

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

提示:

• 1 <= s.length, p.length <= 3 * 104
• s 和 p 仅包含小写字母

A：这类问题本身不复杂，用不定长类的哈希表或者数组都可以解，就是代码繁琐一点。这里重点突出一种特殊解法，来源于该题的最高评论，题目代码较为简单，且称之为消耗品解法，

• 数组版解法，注意check函数设计

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function (s, p) {
    // 不定长滑动窗口
    // 频数数组
    const pattern = new Array(26).fill(0);
    const window = new Array(26).fill(0);
    const aCode = "a".charCodeAt();
    const k = p.length;

    let left = 0;
    let right = 0;
    let distance = 0;
    let match = 0;
    const ans = [];

    // 处理p串
    for (const char of p) {
        pattern[char.charCodeAt() - aCode]++;
    }
    for (const count of pattern) {
        if (count > 0) distance++;
    }

    while (right < s.length) {
        const rIndex = s[right].charCodeAt() - aCode;
        window[rIndex]++;

        if (window[rIndex] == pattern[rIndex]) {
            match++;
        }

        // check函数设计
        // 这里需要长度相同，即满足条件 = 频数 + 长度
        const d = right - left + 1;
        if (d == k && match == distance) {
            ans.push(left);
        }

        if (d >= k) {
            const lIndex = s[left].charCodeAt() - aCode;
            if (window[lIndex] == pattern[lIndex]) {
                match--;
            }
            window[lIndex]--;
            left++;
        }

        right++;
    }

    return ans;
};

• 进阶版解法，消耗品解法，详细可见该题目的官方题解最高评论，需要慢慢体会，异位词类问题都可用该解法，比如567. 字符串的排列 (opens new window)。这种解法是把p串视为一种“消耗品”，只有完全匹配的时候，才能把消耗品消耗完，因此在包含消耗品时就消耗，没有消耗品就增加。虽然不是标准意义上的滑动窗口概念，但是代码比较简介，思路比较巧妙。

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function (s, p) {
    // 核心思路：将它转变为遍历s的时候一种“消耗品”——当“消耗品”不足，唯一可以做的就是移动左窗口释放一些出来。这里面有一个比较特殊的corner case，s中有一个p中没有的字符。下面的代码刚好自洽
    const pattern = new Array(26).fill(0);
    const aCode = "a".charCodeAt();
    for (const char of p) {
        pattern[char.charCodeAt() - aCode]++;
    }

    let low = 0;
    let high = 0;
    const k = p.length;
    const ans = [];
    // 该循环确保[lo, hi)的区间中的出现的字符总是p的一个子集
    while (high < s.length) {
        const highIndex = s[high].charCodeAt() - aCode;
        if (pattern[highIndex] > 0) {
            // 子集条件满足，右移增大窗口
            pattern[highIndex]--;
            high++;

            // 窗口长度 == p.len，且窗口内字符是p的子集
            // <=> (充要条件) s.substring(lo, hi)是p的同字母异序词
            if (high - low == k) {
                ans.push(low);
            }
        } else {
            // 再右移hi不可能满足子集条件，
            // 右移左边界lo、复位计数器，直到这个条件（子集条件）再次满足
            const lowIndex = s[low].charCodeAt() - aCode;
            pattern[lowIndex]++;
            low++;
        }
    }
    return ans;
};

小结

不定长类滑动窗口问题，是滑动窗口中最为常见的题型，该类题型的核心点就是check函数的设计。设计对了check函数，基本上题目也就迎刃而解。这里有几个注意点：

• check函数只是一个概念，泛指满足题目要求的条件，一般当满足条件时，需要记录极值或变量

• 哈希表是基础版的运用，一般来说，都可以用哈希表+check函数来解决该类问题，但是数组或者变量的效率会更高。即这类问题一般有以下几种方案：

  • 哈希表
  • 频数数组
  • 变量
  • 异位词类问题，消耗品解法

• 题目本身可能会叠加很多状态或者限定，导致有一定的迷惑性，一定要仔细分析题目，抓住核心点

附录

不定长类题目

• 3. 无重复字符的最长子串 (opens new window)
• 76. 最小覆盖子串 (opens new window)
• 209. 长度最小的子数组 (opens new window)
• 424. 替换后的最长重复字符 (opens new window)
• 438. 找到字符串中所有字母异位词 (opens new window)
• 567. 字符串的排列 (opens new window)
• 1658. 将 x 减到 0 的最小操作数 (opens new window)
• 1695. 删除子数组的最大得分 (opens new window)