[76] 最小覆盖子串

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。

示例：

输入: S = "ADOBECODEBANC", T = "ABC"

输出: "BANC"

说明：

如果 S 中不存这样的子串，则返回空字符串 ""。

如果 S 中存在这样的子串，我们保证它是唯一的答案。

这是一个经典的滑动窗口题型。解题思路可以参考专题中关于双指针滑动窗口的相关介绍。

按照专题中的思路，这里考虑两点：

1. 扩充右边界后，何时能使滑动窗口内的元素满足要求。根据题意，当滑动窗口的hash map与需求子串的hash map完全相同时，考虑开始缩小左边界。这里为了减少遍历比对hash map 的复杂度，多使用了一个valid字段来记录单字符个数匹配的情况。

2. 何时更新返回结果。在本题中，当滑动窗口的长度恰好等于子串长度，此时可以比对并更新结果。

function minWindow(s: string, t: string): string {
  const initRes = s + ' ';
  let res = initRes;

  const needs: Record<string, number> = {};
  for (let i = 0; i < t.length; i++) {
    const ch = t[i];
    needs[ch] = needs[ch] ? needs[ch] + 1 : 1;
  }
  const needsLength = Object.keys(needs).length;

  const window: Record<string, number> = {};
  let left = 0;
  let right = 0;
  let validCount = 0;
  while (right < s.length) {
    // 扩右边界
    const ch = s[right];
    right++;

    if (needs[ch]) {
      // 更新滑动窗口元素内容以及合法指标判断
      window[ch] = window[ch] ? window[ch] + 1 : 1;
      if (window[ch] === needs[ch]) {
        validCount += 1;
      }
    }

    while (validCount === needsLength) {
      // 若当前滑动窗口中字串长度小于res，则更新res字串
      if (right - left < res.length) {
        res = s.substring(left, right);
      }

      // 缩左边界
      const dropCh = s[left];
      left++;

      // 更新滑动窗口元素内容以及合法指标判断
      if (needs[dropCh] && needs[dropCh] > 0) {
        if (window[dropCh] === needs[ch]) validCount -= 1;
        window[dropCh] -= 1;
      }
    }
  }

  return res === initRes ? '' : res;
}