最小覆盖子串 | Alvin's note

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

注意

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

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"

输入：s = "a", t = "a"
输出："a"

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

思路

使用滑动窗口

用 i,j 表示滑动窗口的左边界和右边界，通过改变 i,j 来扩展和收缩滑动窗口，可以想象成一个窗口在字符串上游走，当这个窗口包含的元素满足条件，即包含字符串 T 的所有元素，记录下这个滑动窗口的长度 j-i+1，这些长度中的最小值就是要求的结果。

不断增加 j 使滑动窗口增大，直到窗口包含了 T 的所有元素
不断增加 i 使滑动窗口缩小，因为是要求最小字串，所以将不必要的元素排除在外，使长度减小，直到碰到一个必须包含的元素，这个时候不能再扔了，再扔就不满足条件了，记录此时滑动窗口的长度，并保存最小值
让 i 再增加一个位置，这个时候滑动窗口肯定不满足条件了，那么继续从步骤一开始执行，寻找新的满足条件的滑动窗口，如此反复，直到 j 超出了字符串 S 范围。

图示

以 S="DOABECODEBANC"，T="ABC" 为例

初始状态：

步骤一：不断增加 j 使滑动窗口增大，直到窗口包含了 T 的所有元素

步骤二：不断增加 i 使滑动窗口缩小，直到碰到一个必须包含的元素 A，此时记录长度更新结果

步骤三：让 i 再增加一个位置，开始寻找下一个满足条件的滑动窗口

代码

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function (s, t) {
  // 双指针滑动窗口问题
  let i = 0;
  let j = 0;
  let result = '';

  let map = {};
  for (const c of t) {
    map[c] = map[c] ? map[c] + 1 : 1;
  }

  let count = Object.keys(map).length;

  // 右移指针
  while (j < s.length) {
    const char = s[j];
    if (map[char] !== undefined) map[char]--;
    // 如果匹配到一个字符，需要再匹配的数量减 1
    if (map[char] === 0) count--;

    while (count === 0) {
      const matchStr = s.slice(i, j + 1);
      if (!result || matchStr.length < result.length) result = matchStr;

      // 如果当前左指针匹配中了
      if (map[s[i]] !== undefined) {
        map[s[i]]++;
        // 注意！这里 count++ 的条件基于当前 map[s[i]] === 1, 否则可能会重复
        if (map[s[i]] === 1) count++;
      }

      i++;
    }
    j++;
  }

  return result;
};

需要注意的细节点

if (map[char] === 0) count--;
if (map[char] === 1) count++;

思路 ​

代码 ​

思路

代码