Meta Permutation in String：定长窗口与差异计数

题目重点：判断文本中是否包含pattern的任意排列，维护字符重数和不匹配键数量。

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

训练大小写敏感，pattern字符顺序任意但重数必须完全相同；空pattern匹配任意text，pattern比text长则False。
示例按字符哈希计数，不局限26小写字母；Unicode按码点，不自动规范化。

解题路线

排列的必要充分条件是窗口长度等于pattern长度且各字符频次相同。窗口必须定长，不能只看包含了pattern所有不同字符。
need构造pattern重数，window构造首窗口；different记录所有键中window[ch]≠need[ch]的数量。different=0即精确匹配。
滑一步先移出旧字符再移入新字符，每次调整某键前减旧差异标记，更新计数后加新标记；即使移出移入同一个字符，也保持不变量。
window计数为0时删除键控制状态规模，Counter缺失查值为0。need只读不能因查询未见字符增加永久键。若只26字符，也可数组加计数diff避免哈希。
不在每个窗口排序或遍历整个alphabet。比较完整Counter虽有时可接受，但最坏每窗口O(D)；different让每次只处理两键。

手动走一遍

pattern=ab，text=eidbaooo在ba窗口命中；eidboaoo不命中。pattern=aab需要两个a，窗口abb虽有a/b两类仍不合法。空pattern直接True。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

from collections import Counter


def contains_permutation(pattern,text):
    """Case-sensitive character multiplicities, empty pattern matches."""
    length=len(pattern)
    if length==0:return True
    if length>len(text):return False
    need=Counter(pattern);window=Counter(text[:length]);different=0
    # Constant-time updates maintain number of keys whose counts differ.
    for ch in need.keys() | window.keys():different+=need[ch]!=window[ch]
    def adjust(ch,delta):
        nonlocal different
        different-=window[ch]!=need[ch]
        window[ch]+=delta
        different+=window[ch]!=need[ch]
        if window[ch]==0:del window[ch]
    if different==0:return True
    for right in range(length,len(text)):
        adjust(text[right-length],-1);adjust(text[right],1)
        if different==0:return True
    return False

复杂度

均摊O(P+N)时间，空间O(Dp+Dw)，Dw≤min(P,字母表规模)，输出bool。Python哈希是平均复杂度，不承诺恶意碰撞下严格最坏常数。

易错点与追问

容易失分的边界

只比较set遗漏字符重数。
更新different只在加新字符时做，移出的旧字符也会改变差异。

继续深挖

返回全部起点只需命中时记录index，输出可能O(N)。
允许通配符的pattern需要怎样修改重数匹配条件？先明确通配符能代表多少字符。