题目

题目来源：力扣（LeetCode）

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


注意：

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

示例 1：

输入：s = “ADOBECODEBANC”, t = “ABC”
输出：”BANC”

示例 2：

输入：s = “a”, t = “a”
输出：”a”

示例 3:

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

思路分析

滑动窗口

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

  1. 我们在字符串 S 中使⽤双指针中的左右指针技巧，初始化 left = right = 0，把索引闭区间 [left,
    right] 称为⼀个「窗⼝」。
  2. 我们先不断地增加 right 指针扩⼤窗⼝ [left, right]，直到窗⼝中的字符串符合要求（包含了 t 中的
    所有字符）
  3. 我们停⽌增加 right，转⽽不断增加 left 指针缩⼩窗⼝ [left, right]，直到窗⼝中的字符串不再符合
    要求（不包含 T 中的所有字符了）。同时，每次增加 left，我们都要更新⼀轮结果
  4. 重复第 2 和第 3 步，直到 right 到达字符串 S 的尽头
  1. /**
  2.  * @param {string} s
  3.  * @param {string} t
  4.  * @return {string}
  5.  */
  6. var minWindow = function(s, t) {
  7.   // 需要的
  8.   let need = {};
  9.   // 窗口中的字符
  10.   let window = {};
  11.   for (let a of t) {
  12.     // 统计需要的字符
  13.     need[a] = (need[a] || 0) + 1;
  14.   }
  15.   // 左右指针
  16.   let left = 0,
  17.     right = 0;
  18.   let valid = 0;
  19.   // 最小覆盖子串的起始索引及长度
  20.   let start = 0,
  21.     len = Number.MAX_VALUE;
  22.   while (right < s.length) {
  23.     // 即将移入窗口的字符
  24.     let c = s[right];
  25.     // 右移窗口
  26.     right++;
  27.     if (need[c]) {
  28.       // 当前字符在需要的字符中，则更新当前窗口统计
  29.       window[c] = (window[c] || 0) + 1;
  30.       if (window[c] == need[c]) {
  31.         // 当前窗口和需要的字符匹配时，验证数量增加1
  32.         valid++;
  33.       }
  34.     }
  35.     // 当验证数量与需要的字符个数一致时，就应该收缩窗口了
  36.     while (valid == Object.keys(need).length) {
  37.       // 更新最小覆盖子串
  38.       if (right - left < len) {
  39.         start = left;
  40.         len = right - left;
  41.       }
  42.       //即将移出窗口的字符
  43.       let d = s[left];
  44.       // 左移窗口
  45.       left++;
  46.       if (need[d]) {
  47.         if (window[d] == need[d]) {
  48.           valid--;
  49.         }
  50.         window[d]--;
  51.       }
  52.     }
  53.   }
  54.   return len == Number.MAX_VALUE ? "" : s.substr(start, len);
  55. };

参考阅读 https://leetcode-cn.com/problems/minimum-window-substring/solution/hua-dong-chuang-kou-tong-yong-jie-ti-tao-9v69/