最小覆盖子串.md

76. 最小覆盖子串

function minWindow(s, t) {
  let need = {},
    window = {};

  // 用 字符串 t 初始化 need, 要考虑重复情况
  [...t].map((c) => (need[c] ? need[c]++ : (need[c] = 1)));

  // 窗口指针的初始化为 0 是一个左闭右开的区间 [left, right)  valid 用来记录窗口中已经满足条件的字符个数
  let left = 0,
    right = 0,
    valid = 0;

  // 最新覆盖子串的开始位置及长度
  let start = 0,
    len = Infinity;
  let keysLength = Object.keys(need).length;

  while (right < s.length) {
    // c 是进入窗口的字符
    let c = s[right];
    // 右移窗口
    right++;

    // 窗口数据更新 如果 c 是符合要求的字符
    if (need[c]) {
      // 更新窗口中的数据
      window[c] ? window[c]++ : (window[c] = 1);
      // 如果窗口中的字符与需要的字符数量相等
      if (window[c] === need[c]) {
        // 计数加一
        valid++;
      }
    }

    // 如果已经满足要求 则需要判断窗口是否需要收缩
    while (valid === keysLength) {
      // 更新最小覆盖子串
      if (right - left < len) {
        start = left;
        len = right - left;
      }
      // d 是即将从窗口中移出的字符
      let d = s[left];
      // 窗口开始收缩
      left++;

      // 开始窗口数据更新
      if (need[d]) {
        if (window[d] === need[d]) {
          valid--;
        }
        window[d]--;
      }
    }
  }

  // 返回最小覆盖子串
  return len === Infinity ? "" : s.substr(start, len);
}