题目描述

给定两个字符串 s 和 t 。返回 s 中包含 t 的所有字符的最短子字符串。如果 s 中不存在符合条件的子字符串，则返回空字符串 "" 。

如果 s 中存在多个符合条件的子字符串，返回任意一个即可。

注意： 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。

测试用例

示例 1：

• 输入：s = "ADOBECODEBANC", t = "ABC"
• 输出："BANC"
• 解释：最短子字符串 "BANC" 包含了字符串 t 的所有字符'A'、'B'、'C'

示例 2：

• 输入：s = "a", t = "a"
• 输出："a"

示例 3：

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

思路

双指针模拟滑动窗口

代码实现

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function (s, t) {
  // 题目要求的是随便任意一个
  // 所以找到一个最优解返回即可

  // 记录需要的 —— 也就是统计 t 中字符
  let need = new Map();
  // window 来记录当前滑动窗口里 需要字符 的状态
  let window = new Map();

  // 初始化need
  for (let i of t) {
    if (need.has(i)) {
      need.set(i, need.get(i) + 1);
    } else {
      need.set(i, 1);
    }
  }
  // 开始遍历
  let left = 0;
  let right = 0;
  let validCnt = 0;
  // 记录满足条件的子串的开始位置 —— 用来存子串
  let start = 0;

  // 记录最小长度
  let len = Number.MAX_VALUE;
  while (right < s.length) {
    let cur = s[right];
    right++;
    // 如果 need 有当前s[right]
    // 则更新滑动窗口
    if (need.has(cur)) {
      if (window.has(cur)) {
        window.set(cur, window.get(cur) + 1);
      } else {
        window.set(cur, 1);
      }
      if (window.get(cur) === need.get(cur)) {
        validCnt++;
      }
    }
    console.log("need: ", need);
    console.log("window: ", window);
    // 包含全部子串元素了
    while (validCnt === need.size) {
      // 如果找到一个更短的子串
      if (right - left < len) {
        start = left;
        len = right - left;
      }
      let now = s[left];
      left++;
      // 如果是需要的子串
      if (need.has(now)) {
        // 看它现在在不在滑动窗口里
        if (window.get(now) === need.get(now)) {
          validCnt--;
        }
        window.set(now, window.get(now) - 1);
      }
    }
  }

  return len === Number.MAX_VALUE
    ? ""
    : s.split("").splice(start, len).join("");
};

console.log(minWindow("ADOBECODEBANC", "ABC"));