题目描述

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

  2. 注意

    • 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
    • 如果 s 中存在这样的子串，我们保证它是唯一的答案。
    • s 和 t 由英文字母组成。
    • m == s.length，n == t.length，1 <= m, n <= 105。

  3. 输入输出示例

    输入-s 输入-t 输出-最小子串
    “ADOBECODEBANC” “ABC” “BANC”
    “a” “a” “a”
    “a” “aa” “”

算法思想（滑动窗口）

该算法的时间复杂度为 O(m+n)，是该问题的最优的时间复杂度！

实现步骤

  1. 定义最小覆盖子串 minSubStr = ""

  2. 初始化窗口

    • 定义两个指针：左指针 left 和右指针 right，分别指向滑动窗口的左右边界
    • 初始情况下，left = 0，right = 0
    • right++ 用于扩展窗口，left++ 用于收缩窗口
    • 窗口子串为 s.slice(left, right + 1)

  3. 扩展窗口：将右指针向右移动，扩展窗口，直到窗口子串是有效子串（即包含 t 中的所有字符）

  4. 收缩窗口：如果窗口子串是有效子串，则尝试将左指针向右移动，直到窗口子串不是有效子串（即不包含 t 中的所有字符）

  5. 循环：回到 Step2，直到右指针 right 到达字符串的末尾

    注-1：每当扩展窗口导致窗口子串是有效子串，则记录并视情况更新最小覆盖子串 minSubStr

    注-2：在窗口收缩的过程中，扩展直到窗口子串有效，收缩直到窗口子串无效，按此反复

窗口有效性判断

  1. 建立 t 的频数统计哈希表 freqT；建立窗口子串的频数统计哈希表 freqWindow；key 为字符，value 为该字符在字符串中的出现频数（次数）
  2. 建立有效字符计数器 matchedCount；当窗口子串的某个字符的频数等于 t 中对应字符的频数时，matchedCount++
  3. 每次移动左右指针时，更新 matchedCount，一旦 matchedCount === freqT.size 时，便认为窗口子串是有效的

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
function minWindow(s: string, t: string): string {
  /* 边界条件 */
  if (t.length === 0 || s.length === 0) return "";
  if (t.length > s.length) return "";

  /* 构建 t 的频数统计哈希表，记录 t 中每个字符的出现次数 */
  const freqT = new Map<string, number>();
  for (let char of t) freqT.set(char, (freqT.get(char) || 0) + 1);

  /* 窗口相关变量初始化 */
  const freqWindow = new Map<string, number>(); // 记录窗口内字符的频数
  let [left, right] = [0, 0]; // 左右指针，分别指向窗口的左右边界
  let matchedCount = 0; // 记录窗口内有效字符的个数
  let minSubStr = ""; // 存储符合条件的最小覆盖子串

  /* 动态扩展和收缩窗口 */
  while (right < s.length) {
    /* 扩展窗口：将右指针指向的字符加入窗口的频数统计中 */
    const rightChar = s[right];
    freqWindow.set(rightChar, (freqWindow.get(rightChar) || 0) + 1);

    /* 如果该字符在 t 中存在，且窗口中该字符的频数达到了 t 中的频数，更新有效字符计数器 */
    if (
      freqT.has(rightChar) &&
      freqWindow.get(rightChar) === freqT.get(rightChar)
    ) {
      matchedCount++;
    }

    /* 收缩窗口：当窗口包含了 t 中所有字符时，尝试收缩窗口 */
    while (matchedCount === freqT.size) {
      /* 更新最小覆盖子串 */
      const minSubStrLen = minSubStr.length || Number.MAX_SAFE_INTEGER;
      if (right - left + 1 < minSubStrLen) minSubStr = s.slice(left, right + 1);

      /* 移动左指针，收缩窗口 */
      const leftChar = s[left];
      freqWindow.set(leftChar, freqWindow.get(leftChar)! - 1); // 减少窗口中左侧字符的频数

      /* 如果该字符在 t 中存在，且频数低于 t 中要求的频数，减少有效字符计数器 */
      if (
        freqT.has(leftChar) &&
        freqWindow.get(leftChar)! < freqT.get(leftChar)!
      ) {
        matchedCount--;
      }
      left++; // 左指针右移，进一步收缩窗口
    }

    right++; // 右指针右移，继续扩展窗口
  }

  return minSubStr; // 返回找到的最小覆盖子串，若没有则返回空字符串
}