76-最小覆盖子串.md

76-最小覆盖子串

原题 s 字符串中含有 t 字符串所有字母的子串(可乱序)，最短是哪个 题解参考

const minWindow = function (s, t) {
  let minLen = s.length + 1;
  let start = s.length;
  let map = {};
  let missingType = 0;
  for (const c of t) {
    if (!map[c]) {
      missingType++;
      map[c] = 1;
    } else {
      map[c]++;
    }
  }

  let l = 0,
    r = 0;
  for (; r < s.length; r++) {
    let rightChar = s[r];
    if (map[rightChar] !== undefined) {
      map[rightChar]--;
    }
    // 也就是遍历到这一步的时候，所有的数字都找到了，这时候右边界已经确定了
    // 然后开始通过下面的 while 来找到左边界
    if (map[rightChar] === 0) {
      missingType--;
    }

    while (missingType === 0) {
      if (r - l + 1 < minLen) {
        minLen = r - l + 1;
        start = l;
      }

      // 还是没有明白这两个 if 条件语句是要用来干嘛
      // 应该是用来判断退出 while 的边界条件
      // 也就是不断将左边界右移，一旦发现右移的时候，遇到了需要匹配的字符串，就中断

      // 也不是说遇到了匹配的字符串就中断，因为如果全部拿到了匹配的字符串后，部分字符串可能匹配的次数多余需要匹配的次数
      // 所以在上面有 map[rightChar]--，可能到最终 map[rightChar] 是个负数
      // 所以在这里我们需要保证次数，通过map[leftChar]++，如果map[leftChar]大于0了就退出

      /* 
        是因为上面是当 missingType === 0 进入时候的计算，然后需要继续往后走，所以这里主要的是 l++，然后 l++ 之后，会带来什么情况
        也就是在当前字符串中，如果去掉了 s[l] 会有什么情况，这两个 if 就是在计算这种情况
      */
      let leftChar = s[l];
      if (map[leftChar] !== undefined) {
        map[leftChar]++;
      }
      if (map[leftChar] > 0) {
        missingType++;
      }

      l++;
    }
  }

  if (start === s.length) {
    return '';
  }

  return s.substring(start, start + minLen);
};

let s = 'ADOBECODEBANC',
  t = 'ABC';
let result = minWindow(s, t);
console.log(result);