数据结构与算法 / 系统课时

用频次差解决字符串窗口

用频次差解决字符串窗口

字符串滑窗题的难点常常不是移动指针,而是快速判断当前窗口“还缺哪些字符”。本篇把覆盖串和异位词统一成频次差模型,用一个 missing 状态把复杂比较压缩成常数级判断。

学习目标

  • 用字符频次差描述窗口相对目标串的缺口
  • 理解字符进入与离开窗口时 missing 的更新条件
  • 将同一模型迁移到最小覆盖串与异位词匹配

把窗口改写成缺口问题

设 need[c] 表示目标串还需要多少个字符 c。当右端字符进入窗口时,先看它是否仍然是“真正缺少”的字符:只有 need[c] > 0 时,missing 才减一;随后无论是否缺少,都执行 need[c] -= 1。

这样一来,need[c] < 0 表示窗口里字符 c 过量,need[c] == 0 表示数量刚好够,而 missing == 0 表示目标串中的每个字符都已经被当前窗口覆盖。

频次差与 missing 状态的更新流程

这里把 missing 定义成“还缺多少个字符实例”,而不是“还缺多少种字符”。例如目标串是 AABC,初始 missing 应为 4,因为两个 A 都必须被覆盖。

用频次差求最小覆盖串

下面的实现处理经典问题:在 s 中找到覆盖 t 全部字符且长度最短的子串。Counter 对不存在的键返回 0,因此窗口里出现目标串之外的字符也可以直接计数。

python
from collections import Counter


def min_window(s, t):
    if not t or not s:
        return ""

    need = Counter(t)
    missing = len(t)
    left = 0
    best_len = len(s) + 1
    best_start = 0

    for right, ch in enumerate(s):
        # 只有目标仍缺少 ch 时,这次进入才真正缩小总缺口。
        if need[ch] > 0:
            missing -= 1
        need[ch] -= 1

        # 覆盖已经成立,持续收缩以找到当前 right 下的最短窗口。
        while missing == 0:
            current_len = right - left + 1
            if current_len < best_len:
                best_len = current_len
                best_start = left

            left_ch = s[left]
            need[left_ch] += 1
            if need[left_ch] > 0:
                missing += 1
            left += 1

    if best_len == len(s) + 1:
        return ""
    return s[best_start:best_start + best_len]


print(min_window("ADOBECODEBANC", "ABC"))

预期输出

text
BANC

关键点在左端移出字符时:必须先执行 need[left_ch] += 1,再判断它是否变为正数。若变为正数,说明窗口刚刚失去了一个目标所需字符,missing 才需要加一。

异位词只是定长版本

寻找所有异位词时,目标仍然是让窗口频次与模式串一致,但窗口长度固定为 len(t)。因此可以继续维护同一份频次差,只是收缩条件不再是 missing == 0,而是“窗口长度超过目标长度就移出左端”。

当窗口长度恰好等于 len(t) 且 missing == 0 时,就说明这个窗口包含目标串所需的全部字符;由于长度也完全相同,不可能再夹带多余字符,因此它就是一个异位词窗口。

最容易写错的两个判断

字符进入窗口时,判断必须发生在 need[ch] -= 1 之前;否则原本刚好还缺一个的字符会先变成 0,导致 missing 没有减少。

字符离开窗口时则相反:要先执行 need[left_ch] += 1,再判断是否大于 0。这两个方向看似对称,实际判断顺序正好相反,是覆盖串代码最常见的边界错误。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用频次差解决字符串窗口

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通