Permutation in String

Q: 字符串中的排列问题的时间复杂度是多少？

使用滑动窗口时，时间复杂度为 O(m + n) ，其中 m 是 s1 的长度， n 是 s2 的长度。你只需统计一次 s1 ，然后 s2 中的每个字母都会进入窗口一次并离开窗口一次。每次都从头统计整个窗口，时间复杂度则为 O(n · m) 。

Q: 在字符串中查找排列，和在字符串中查找字母异位词是一回事吗？

是的。 s1 的一个排列就是它的一个字母异位词，所以问题在于 s2 中是否存在一个长度为 m 的子字符串，它是 s1 的字母异位词。检查整个字符串是否互为字母异位词时，只需比较一次字符计数；这里则是在滑动窗口中进行检查。

中等滑动窗口哈希

+10

一个字符串的排列会使用相同的字母，顺序可以不同，每个字母出现的次数与原字符串相同：tar、rat 和 art 互为排列。给你两个由小写英文字母组成的字符串 s1 和 s2。如果 s1 的某种排列作为子字符串（连续的一段字符）出现在 s2 中，则返回 true；否则返回 false。

函数

checkInclusion(s1: string, s2: string) → boolean

s1string: 要重新排列的字母
s2string: 要在其中搜索的字符串
返回值boolean: 当 s2 的某个子字符串是 s1 的一种重新排列时为 true

约束条件

1 ≤ s1.length ≤ 2 × 10⁴
1 ≤ s2.length ≤ 5 × 10⁴
s1 和 s2 中只包含小写英文字母（从 a 到 z）。
s1 的长度可能大于 s2。

示例

输入: s1 = "tar"s2 = "smartphone"
输出: true
解释: smartphone 中索引 2 到 4 处的子字符串 art 包含一个 a、一个 r 和一个 t，这些字母与 tar 相同。

输入: s1 = "noon"s2 = "onion"
输出: false
解释: 长度为 4 的窗口是 onio 和 nion。noon 需要两个 n 和两个 o，而每个窗口都有一个 i 替代了其中一个字母。

输入: s1 = "abcd"s2 = "dcb"
输出: false
解释: abcd 的任意排列都有 4 个字母，而 dcb 只有 3 个字母，所以它不可能包含其中一个。

进阶

你能否在 O(m + n) 时间内，返回 s2 中所有以 s1 的某种排列开头的索引？

提示

逐个打开提示，每个都会多透露一点。

已打开 0/3

题解

列出所有排列毫无希望：10 个字母就已经有 3,628,800 种排列。忽略顺序即可。s2 的子字符串恰好在长度为 m 且每个字母的数量都与 s1 相同时，才是 s1 的一个排列。因此，让一个长度为 m 的窗口在 s2 中滑动，每一步都更新计数，让一个字母进入窗口，同时让一个字母离开窗口。

从头开始计算每个窗口

结果正确，但无法在最大的测试中运行完毕

思路

先用一个包含 26 个数字的表统计 s1 中每个字母出现的次数。然后取出 s2 中每个长度为 m 的子字符串，在一个新的表中统计其中每个字母出现的次数，再进行比较。在 smartphone 中，窗口依次是 sma、mar、art 等，其中 art 与 tar 匹配。

这种方法会检查每个候选项，因此结果正确。但相邻窗口有 m-1 个字母相同，你却要把这些字母全部重新统计一遍：当 m = 2 × 10^4 且 n = 5 × 10^4 时，会有 30,001 个窗口，每个窗口包含 20,000 个字母，总共约需 6 × 10^8 步。

算法

如果 s1 比 s2 长，返回 false。
在一个包含 26 个零的表 need 中统计 s1 中各字母的数量。
对于从 0 到 n-m 的每个起始索引，在一个新表中统计从该起始位置开始的 m 个字符中各字母的数量。
如果该表等于 need，返回 true。
检查完最后一个窗口后，返回 false。

def checkInclusion(s1, s2):
    m, n = len(s1), len(s2)
    if m > n:
        return False
    need = [0] * 26  # need[0] is 'a', need[25] is 'z'
    for ch in s1:
        need[ord(ch) - 97] += 1
    for start in range(n - m + 1):
        # Count the letters of s2[start : start + m] from scratch
        window = [0] * 26
        for i in range(start, start + m):
            window[ord(s2[i]) - 97] += 1
        if window == need:
            return True
    return False

滑动窗口并比较 26 个计数

思路

相邻窗口有两个字母不同：从 mar 移到 art，会移除 m 并添加 t。因此，只需为当前窗口维护一张表，并在每一步通过一次 +1 和一次 -1 来更新它。

无论 m 是多少，每一步都需要两次更新，并比较 26 个数字：在最大输入规模下，大约需要 26 × 50,000 = 1.3 × 10^6 次运算。

算法

如果 s1 比 s2 长，返回 false。
统计 s1 中各字符的数量，存入 need；统计 s2 前 m 个字母的数量，存入 window。
如果这两个表相等，返回 true。
对于从 m 到 n-1 的每个 i：将 s2[i] 的计数加 1，将 s2[i-m] 的计数减 1；如果这两个表相等，则返回 true。
返回 false。

def checkInclusion(s1, s2):
    m, n = len(s1), len(s2)
    if m > n:
        return False
    need = [0] * 26
    window = [0] * 26
    for i in range(m):
        need[ord(s1[i]) - 97] += 1
        window[ord(s2[i]) - 97] += 1  # the first window is s2[0 : m]
    if window == need:
        return True
    for i in range(m, n):
        window[ord(s2[i]) - 97] += 1      # s2[i] enters on the right
        window[ord(s2[i - m]) - 97] -= 1  # s2[i - m] leaves on the left
        if window == need:
            return True
    return False

滑动窗口并跟踪不平衡的字母

思路

每一步只会改变两个计数，因此比较全部 26 个计数会重复做很多工作。维护 balance[c]，即 s1 中 c 的数量减去当前窗口中的数量；再维护 unbalanced，即平衡值不为 0 的字母数量。窗口恰好是 s1 的一个排列，当且仅当 unbalanced 为 0。

用一条规则确保计数器正确：改变平衡值之前，如果它为 0，就给 unbalanced 加 1；改变之后，如果它为 0，就减 1。从 2 变为 1 时不会触发任何操作，这是正确的。对于 smartphone 中的 tar，unbalanced 初始为 3。s 和 m 会让它增至 5，a 会使它降至 4，加入 r 并移出 s 后变为 2，再加入 t 并移出 m 后，在 art 处变为 0。

你可以从第一个字母开始检查：当窗口长度小于 m 时，所有平衡值之和为正数，因此其中至少有一个不为 0。

算法

如果 s1 比 s2 长，返回 false。
将 s1 计入 balance，并将 unbalanced 设置为余额不为 0 的字母数量。
对于 s2 的每个索引 i，将 s2[i] 的余额减 1。如果余额原本为 0，则将 unbalanced 加 1；如果余额变为 0，则将其减 1。
如果 i ≥ m，按照相同的方式处理，将 s2[i-m] 的余额加 1。
如果 unbalanced 为 0，返回 true。循环结束后，返回 false。

def checkInclusion(s1, s2):
    m, n = len(s1), len(s2)
    if m > n:
        return False
    # balance[c]: copies of letter c in s1 minus copies in the window
    balance = [0] * 26
    for ch in s1:
        balance[ord(ch) - 97] += 1
    unbalanced = sum(1 for b in balance if b != 0)
    for i in range(n):
        # s2[i] enters the window on the right
        c = ord(s2[i]) - 97
        if balance[c] == 0:
            unbalanced += 1
        balance[c] -= 1
        if balance[c] == 0:
            unbalanced -= 1
        # s2[i - m] leaves on the left once the window would pass m letters
        if i >= m:
            c = ord(s2[i - m]) - 97
            if balance[c] == 0:
                unbalanced += 1
            balance[c] += 1
            if balance[c] == 0:
                unbalanced -= 1
        if unbalanced == 0:
            return True
    return False

易错点和边界情况

只检查 s1 中的每个字母是否都在窗口内。onio 包含 noon 中的每个字母，但它并不是 noon 的一个排列。
移除了错误的字母。s2[i] 进入窗口时，s2[i-m] 离开窗口；移除 s2[i-m+1] 会删掉仍在窗口内的字母。
跳过了第一个窗口。如果只在滑动后进行比较，就永远找不到 tarp 中索引 0 处的 tar。
当 s1 比 s2 长时，没有先返回 false。在 Rust 中，对无符号长度执行 n - m 会发生下溢；在 Swift 中，范围 0...(n - m) 会导致崩溃。
在使用 == 比较数组时，比较的是引用，例如 JavaScript 和 Dart 中的情况。在 Java 中使用 Arrays.equals。

常见问题3

字符串中的排列问题的时间复杂度是多少？

使用滑动窗口时，时间复杂度为 O(m + n)，其中 m 是 s1 的长度，n 是 s2 的长度。你只需统计一次 s1，然后 s2 中的每个字母都会进入窗口一次并离开窗口一次。每次都从头统计整个窗口，时间复杂度则为 O(n · m)。

在字符串中查找排列，和在字符串中查找字母异位词是一回事吗？

是的。s1 的一个排列就是它的一个字母异位词，所以问题在于 s2 中是否存在一个长度为 m 的子字符串，它是 s1 的字母异位词。检查整个字符串是否互为字母异位词时，只需比较一次字符计数；这里则是在滑动窗口中进行检查。

我可以用哈希表代替由 26 个计数器组成的数组吗？

是的，如果字符串可以包含任意字符，你就需要使用它。如果只包含小写字母，长度为 26 的数组会更快。使用映射时，当某个键的计数降到 0 时就删除它，这样字母相同的映射比较起来才相等；你也可以使用 unbalanced 计数器，它在映射中也能以同样的方式工作。

def checkInclusion(s1, s2):
    # 在这里编写代码

测试 #1

测试 #2

测试 #3

参数

s1 = "tar"
s2 = "smartphone"

预期输出

true