Permutation in String

判断一个字符串是否包含另一个字符串的某个排列。

判断 s2 是否包含 s1 的某个排列。因为任何合法答案的长度都固定为 |s1|，所以这是一道定长窗口题，而不是变长窗口题。

StringSliding Window

题目定位

因为目标排列长度固定，所以这是非常标准的定长滑动窗口加频次匹配题。

关键观察

任何合法排列窗口长度都必须等于 s1，因此题目就变成：是否存在一个固定长度窗口，其字符频次刚好匹配。

目标复杂度

O(n) / O(1)

这题的解法思路怎么拆

先统计 s1 需要的字符频次。

在 s2 上维护一个长度固定为 s1.length 的窗口。

每次窗口进入或移出一个字符，都同步更新频次差值。

只要有某一刻所有频次都匹配，就说明存在一个排列。

拿一个例子顺一遍

例如 s1 = "ab", s2 = "eidbaooo"。

窗口先经过 "ei"、"id"，都不匹配。

当窗口来到 "ba" 时，字符频次和 s1 完全一致。

因此答案为 true。

参考实现

Python

from collections import Counter

def checkInclusion(s1: str, s2: str) -> bool:
    window_length = len(s1)
    if window_length > len(s2):
        return False

    need = Counter(s1)
    window = Counter(s2[:window_length])
    if window == need:
        return True

    for right in range(window_length, len(s2)):
        left_char = s2[right - window_length]
        window[left_char] -= 1
        if window[left_char] == 0:
            del window[left_char]

        window[s2[right]] += 1
        if window == need:
            return True

    return False