/*
当前函数是一张`map` 同时表示「还缺几个」和「多出来几个」，所以`map[c]` 可能变成负数，理解成本高。更直观的版本是：

`need` ：`t` 里每个字符需要几个
`window` ：当前窗口里每个字符已有几个
`valid` ：已有数量满足需求的字符种类数

*/
const minWindow = function (s, t) {
  if (s.length === 0 || t.length === 0) return '';

  const need = {};
  const window = {};

  for (const c of t) {
    need[c] = (need[c] || 0) + 1;
  }

  const needKinds = Object.keys(need).length;
  let valid = 0;
  let left = 0;
  let start = -1;
  let minLen = s.length + 1;

  for (let right = 0; right < s.length; right++) {
    const c = s[right];

    if (need[c] !== undefined) {
      window[c] = (window[c] || 0) + 1;

      if (window[c] === need[c]) {
        valid++;
      }
    }

    while (valid === needKinds) {
      // 判断边界条件
      const len = right - left + 1;
      if (len < minLen) {
        minLen = len;
        start = left;
      }

      // 窗口左移
      const d = s[left];
      if (need[d] !== undefined) {
        if (window[d] === need[d]) {
          valid--;
        }
        window[d]--;
      }

      left++;
    }
  }

  return start === -1 ? '' : s.substring(start, start + minLen);
};

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);