字符覆盖：异位词与最小覆盖子串

整理来源：前端高频算法原题解析.pdf、第二篇 - 大厂面试手写题及算法.pdf、第四篇 - 面试高频踩坑解析.pdf 的滑动窗口部分。保留可复核的题面和实现，过滤宣传内容与无法验证的数字。

1. 固定窗口：找到所有字母异位词

异位词的窗口长度固定为模式串长度，且每个字符的频次必须相等。用 matchedKinds 记录“频次刚好达到目标”的字符种类，避免每次都比较整张 Map：

function findAnagrams(text, pattern) {
  const source = [...text]
  const target = [...pattern]
  if (target.length === 0 || source.length < target.length) return []

  const need = new Map()
  for (const char of target) need.set(char, (need.get(char) ?? 0) + 1)

  const window = new Map()
  const result = []
  let matchedKinds = 0

  const add = (char) => {
    if (!need.has(char)) return
    const expected = need.get(char)
    const current = window.get(char) ?? 0
    if (current === expected) matchedKinds -= 1
    const next = current + 1
    window.set(char, next)
    if (next === expected) matchedKinds += 1
  }

  const remove = (char) => {
    if (!need.has(char)) return
    const expected = need.get(char)
    const current = window.get(char)
    if (current === expected) matchedKinds -= 1
    const next = current - 1
    if (next === 0) window.delete(char)
    else window.set(char, next)
    if (next === expected) matchedKinds += 1
  }

  for (let right = 0; right < source.length; right += 1) {
    add(source[right])
    if (right >= target.length) remove(source[right - target.length])
    if (right >= target.length - 1 && matchedKinds === need.size) {
      result.push(right - target.length + 1)
    }
  }

  return result
}

每个字符最多入窗和出窗一次，时间复杂度为 O(n + m)；由于示例把字符串展开为 code point 数组，辅助空间为 O(n + m + k)（不计结果数组时仍包含展开数组）。返回索引时要先约定索引是 Unicode code point 还是 JavaScript code unit；上面的 [...] 按 code point 处理，适合常见字符题，但不等于完整的用户感知字符（grapheme）分割。

2. 可变窗口：最小覆盖子串

窗口需要覆盖目标串的全部字符和频次。formed 表示已经满足频次的字符种类数；右边界扩张到可行后，持续收缩左边界，直到刚好失去覆盖：

function minWindow(text, target) {
  const source = [...text]
  const required = [...target]
  if (required.length === 0 || source.length < required.length) return ''

  const need = new Map()
  for (const char of required) need.set(char, (need.get(char) ?? 0) + 1)

  const window = new Map()
  let formed = 0
  let left = 0
  let bestStart = 0
  let bestLength = Infinity

  for (let right = 0; right < source.length; right += 1) {
    const incoming = source[right]
    if (need.has(incoming)) {
      const next = (window.get(incoming) ?? 0) + 1
      window.set(incoming, next)
      if (next === need.get(incoming)) formed += 1
    }

    while (formed === need.size && left <= right) {
      const length = right - left + 1
      if (length < bestLength) {
        bestLength = length
        bestStart = left
      }

      const outgoing = source[left]
      if (need.has(outgoing)) {
        const current = window.get(outgoing)
        if (current === need.get(outgoing)) formed -= 1
        if (current === 1) window.delete(outgoing)
        else window.set(outgoing, current - 1)
      }
      left += 1
    }
  }

  return bestLength === Infinity
    ? ''
    : source.slice(bestStart, bestStart + bestLength).join('')
}

例如 minWindow('ADOBECODEBANC', 'ABC') 返回 BANC。重复字符是关键边界：目标为 AABC 时，窗口中必须有两个 A；只比较 Map.size 会错误地把缺少数量的窗口当成可行。

每个位置最多被左右指针各访问一次，时间复杂度为 O(n + m)；source、required 展开数组和窗口计数共同占用 O(n + m + k) 辅助空间，返回的最短字符串另计输出空间。

3. 固定窗口与可变窗口的区别

问题	窗口长度	收缩条件	答案更新时机
异位词	固定为模式长度	新元素进入后移出最左元素	窗口完整且频次相等
最小覆盖	不固定	已覆盖目标时尽量右移左边界	每次仍覆盖时记录更短窗口
最长无重复子串	不固定	重复约束被破坏时收缩	每次恢复合法后记录最大长度

常见坑

空模式串要单独定义；不要让 right - left === 0 的初始化掩盖边界。
formed 只在“从不足到刚好”和“从刚好到不足”时变化，超过目标频次不能重复计数。
固定窗口先加右端再移除左端，索引和窗口长度要保持一致。
Map 中的键若来自对象或规范化字符串，要明确相等规则；不要用 Object 的原型键承担任意输入。
先写一个暴力版本做小样本对拍，再验证重复字符、目标不存在、目标包含非 ASCII 字符和窗口恰好在首尾的情况。

相关专题：滑动窗口基础知识速览、最长无重复子串、单调队列：滑动窗口最大值。