覆盖型滑动窗口

覆盖型窗口与普通不定长窗口有什么区别？

• 目标: 让窗口内包含目标串 t 的全部字符及其数量;
• 判定条件不是单一数值, 而是"还缺多少种字符"的计数 miss;
• 求解分两阶段: 先扩张到覆盖, 再收缩到刚好覆盖, 取最短窗口;

如何维护"欠账"状态？

• need: 每个目标字符还缺多少个;
• miss: 还缺多少种字符;
  • 某字符欠数由 1 变为 0 时 miss 减一;
  • 该字符最终要向右移动, 要回到欠数大于 0 才能增加 miss;
• miss 为 0 表示窗口已覆盖 t;

最小覆盖子串如何实现？

function minWindow(s: string, t: string): string {
  const need: Record<string, number> = {};
  let miss = 0;
  for (const ch of t) {
    if (need[ch]) need[ch] += 1;
    else {
      need[ch] = 1;
      miss++;
    }
  }

  let left = 0;
  let right = 0;
  let start = 0;
  let min = s.length + 1;
  while (right < s.length) {
    if (need[s[right]] != null) need[s[right]]--;
    if (need[s[right]] === 0) miss--;

    while (miss === 0) {
      if (right - left + 1 < min) {
        start = left;
        min = right - left + 1;
      }
      if (need[s[left]] != null) need[s[left]]++;
      if (need[s[left]] > 0) miss++;
      left++;
    }
    right++;
  }

  return min === s.length + 1 ? "" : s.slice(start, start + min);
}

覆盖型窗口的复杂度是多少？

• 时间复杂度: O(n), right 与 left 各自单向移动;
• 空间复杂度: O(s 与 t 的字符集大小);