LeetCode Hot 100：最小覆盖子串 (2026)

本期讲 LeetCode Hot 100 的「最小覆盖子串」。题目给出字符串 s 和 t，要求返回 s 中包含 t 全部字符的最短子串；t 里的重复字符也必须计入，找不到时返回空字符串。原题还要求尝试做到 O(m + n)。1 这道题收录于 LeetCode 热题 100。

核心是可变长度滑动窗口：right 先扩张到窗口覆盖 t，left 再不断收缩并更新最短答案，直到窗口刚好失效。matched 按字符个数计数，所以能正确处理 t 中的重复字符。

function minWindow(s, t) {
  if (s.length < t.length) return "";

const need = new Map();
  for (const ch of t) {
    need.set(ch, (need.get(ch) || 0) + 1);
  }

const window = new Map();
  let left = 0;
  let right = 0;
  let matched = 0;
  let bestStart = 0;
  let bestLen = Infinity;

while (right < s.length) {
    const inChar = s[right];
    window.set(inChar, (window.get(inChar) || 0) + 1);

if (
      need.has(inChar) &&
      window.get(inChar) <= need.get(inChar)
    ) {
      matched++;
    }
    right++;

while (matched === t.length) {
      if (right - left < bestLen) {
        bestLen = right - left;
        bestStart = left;
      }

const outChar = s[left];
      window.set(outChar, window.get(outChar) - 1);

if (
        need.has(outChar) &&
        window.get(outChar) < need.get(outChar)
      ) {
        matched--;
      }
      left++;
    }
  }

return bestLen === Infinity
    ? ""
    : s.slice(bestStart, bestStart + bestLen);
}

left 和 right 都只向右移动一次，时间复杂度是 O(m + n)。两个 Map 最多记录字符集中的不同字符，空间复杂度是 O(|Σ|)。

References

1
力扣 76. 最小覆盖子串
leetcode.cn

References

Related content