76.最小覆盖子串

最小覆盖子串

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• m == s.length
• n == t.length
• 1 <= m, n <= $10^5$
• s 和 t 由英文字母组成

解析

滑动窗口：右指针扩张窗口直到包含所有字符，然后左指针收缩窗口寻找最小解。

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function (s, t) {
  const need = {};
  for (const c of t) need[c] = (need[c] || 0) + 1;

  let left = 0;
  let minLen = Infinity;
  let minStart = 0;
  let count = t.length; // 还需要匹配的字符数

  for (let right = 0; right < s.length; right++) {
    if (need[s[right]] !== undefined) {
      if (need[s[right]] > 0) count--;
      need[s[right]]--;
    }

    while (count === 0) {
      if (right - left + 1 < minLen) {
        minLen = right - left + 1;
        minStart = left;
      }
      if (need[s[left]] !== undefined) {
        need[s[left]]++;
        if (need[s[left]] > 0) count++;
      }
      left++;
    }
  }

  return minLen === Infinity ? "" : s.substring(minStart, minStart + minLen);
};

滑动窗口的经典应用。时间复杂度 O(m+n)，空间复杂度 O(字符集大小)。