LeetCode LCR 014. 字符串的排列

2026-03-28 HGNULB 约 8 分钟

文章信息 5 个分类 5 个标签

分类

LeetCode 中等 119 经典题变种挑战剑指 Offer 剑指 Offer（专项突击版）

题目描述

✅ LCR 014. 字符串的排列

题意分析

给两个字符串 s1 和 s2，判断 s2 是否包含 s1 的某个排列。换句话说：s2 中是否存在一个连续子串，它恰好是 s1 里全部字符的一次重新排列。

「排列」这个词是全题的钥匙。两个字符串互为排列，当且仅当它们长度相同且每种字符的出现次数完全一致——顺序信息完全无关。于是问题被翻译成：s2 中是否存在一个长度恰为 |s1| 的窗口，其字符频次向量与 s1 的频次向量相等。

「长度固定」是第二个关键信号。绝大多数滑动窗口题的窗口长度是可变的、由某个条件驱动收缩；而这里窗口长度被死死钉在 |s1| 上，于是窗口的移动变成了最简单的形式：右边进一个、左边出一个，两个指针同步前进，不需要任何收缩循环。

字符集限定为小写字母，只有 26 种，因此频次向量可以用长度 26 的定长数组表示，比较两个向量是 $O(26)$ 的常数操作。数据规模 $ s1 , s2 \le 10^4$，$O(26n)$ 完全够用。

边界只有一处但必须先处理：|s1| > |s2| 时不可能存在这样的窗口，直接返回 false；否则建初始窗口时就会越界。另外注意题目要的是存在性，一旦命中即可返回，不需要继续扫。

解法：滑动窗口维护区间

核心思路

暴力做法是枚举 s2 中每个长度为 |s1| 的起点，把该子串排序或统计频次后与 s1 比较。设 $m = s1 $、$n = s2 $，代价是 $O(nm)$ 或 $O(nm\log m)$。瓶颈很清楚：相邻两个窗口只差首尾两个字符，频次却被从头重新统计了一遍。

观察到这一点，改造就很直接：维护一个长度 26 的计数数组 cnt2 表示当前窗口内各字符出现的次数，窗口右移一格时只做两次修改——新进来的字符计数加一、被挤出去的字符计数减一。这样每步都是 $O(1)$ 的更新加一次 $O(26)$ 的比较，总代价 $O(26n)$。

要维护的不变量是：cnt2 恒等于 s2 中当前长度为 m 的窗口的字符频次；cnt1 是 s1 的字符频次，建好后全程不变。判定条件就是两个数组逐位相等。

实现上分成两段。第一段建初始窗口：同时扫 s1 的全部字符和 s2 的前 m 个字符，把两个计数数组一次填好，然后立刻比较一次——这一次比较对应的是起点为 $0$ 的窗口，不能漏。第二段从下标 m 开始逐格右移：先 cnt2[s2[i]]++（右端进），再 cnt2[s2[i - m]]--（左端出），窗口重新变回长度 m，然后比较。

「先进后出」的顺序在这里并不影响正确性（两次修改互不干扰），但把它固定下来有助于保持「比较时窗口长度恰为 m」这条不变量：两次修改必须都完成之后才能比较，中间比较会拿到长度 m + 1 的窗口。

解题步骤

先判 m > n 直接返回 false。这不是可选的优化，而是防止建初始窗口时 s2.charAt(i) 越界。

开两个长度 26 的计数数组。定长数组而不是哈希表，是因为字符集已知且很小，数组的常数远小于哈希，且可以整体比较。

一个循环同时填 cnt1 与 cnt2 的前 m 位。两者长度相同，合并成一趟扫描既短又不易写错下标。

建完初始窗口立刻比较一次。若漏掉，s1 = "ab"、s2 = "ba..." 这种答案就在起点的用例会被判错。

从 i = m 开始右移，每步先加入 s2[i]、再移除 s2[i - m]。i - m 就是即将离开窗口的那个下标：窗口在加入 s2[i] 后覆盖 $[i-m, i]$ 共 m + 1 个字符，移除左端后恰好回到 m 个。

每次移动后比较 cnt1 与 cnt2，相等即返回 true。比较必须在两次修改之后，此刻窗口长度才是 m。

循环走完仍未命中就返回 false。

以 s1 = "ab"、s2 = "eidbaooo" 走一遍，期望 true。m = 2、n = 8，不满足 m > n。建表：cnt1 中 a 和 b 各为 $1$；cnt2 取 s2 的前两位 "ei"，e 和 i 各为 $1$。首次比较不相等。i = 2：加入 s2[2] = 'd'，移除 s2[0] = 'e'，窗口变成 "id"，不相等。i = 3：加入 'b'，移除 s2[1] = 'i'，窗口变成 "db"，不相等。i = 4：加入 'a'，移除 s2[2] = 'd'，窗口变成 "ba"，此时 cnt2 中 a 和 b 各为 $1$，与 cnt1 完全一致，返回 true——注意窗口内容是 "ba" 而 s1 是 "ab"，顺序不同但频次相同，这正是「排列」的定义。整个过程每步只改两个计数位，从未重新统计过整个窗口。

代码实现

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();
        // 长度不够时不可能存在窗口，且能防止下面建表越界。
        if (m > n) {
            return false;
        }
        int[] cnt1 = new int[26];
        int[] cnt2 = new int[26];
        // 一趟填好 s1 的频次与 s2 的首个窗口。
        for (int i = 0; i < m; ++i) {
            ++cnt1[s1.charAt(i) - 'a'];
            ++cnt2[s2.charAt(i) - 'a'];
        }
        // 起点为 0 的窗口也是候选，不能漏比。
        if (Arrays.equals(cnt1, cnt2)) {
            return true;
        }
        for (int i = m; i < n; ++i) {
            // 右端进、左端出，两次修改后窗口长度重新回到 m。
            ++cnt2[s2.charAt(i) - 'a'];
            --cnt2[s2.charAt(i - m) - 'a'];
            if (Arrays.equals(cnt1, cnt2)) {
                return true;
            }
        }
        return false;
    }
}

func checkInclusion(s1 string, s2 string) bool {
    m, n := len(s1), len(s2)
    if m > n {
        return false
    }
    // 定长数组在 Go 里可直接用 == 比较，天然是值语义。
    var cnt1, cnt2 [26]int
    for i := 0; i < m; i++ {
        cnt1[s1[i]-'a']++
        cnt2[s2[i]-'a']++
    }
    if cnt1 == cnt2 {
        return true
    }
    for i := m; i < n; i++ {
        cnt2[s2[i]-'a']++
        cnt2[s2[i-m]-'a']--
        if cnt1 == cnt2 {
            return true
        }
    }
    return false
}

复杂度分析

时间复杂度：$O(26n + m)$，即 $O(n + m)$。窗口右移 $n - m$ 次，每次做两次常数级计数更新和一次长度 26 的数组比较；建表是 $O(m)$。凭的是增量更新——相邻窗口只差两个字符，绝不重新统计整段。

空间复杂度：$O(1)$。两个长度 26 的定长数组，与输入规模无关；没有使用任何哈希表或子串拷贝。

关键点总结

「是否为排列 / 异位词」一律等价于「长度相同且字符频次向量相等」，看到这类字眼就该立刻把顺序信息丢掉，只保留计数。

窗口长度固定时，滑动窗口退化成最简单的形态：没有收缩循环，只有同步的一进一出。识别出「定长」能省掉一整层 while，也消除了「答案在收缩前还是收缩后更新」这个常见坑。

字符集有限时用定长计数数组而不是哈希表：常数小、可整体比较，Go 里数组还是值类型可以直接用 ==。

建好首个窗口后必须立刻比较一次，否则起点为 $0$ 的答案会被漏掉。这是所有「先建窗口再滑动」写法的固定收尾。

离开窗口的下标是 i - m，把它和「窗口覆盖 $[i-m+1, i]$」这个区间对应起来，就不会写成 i - m + 1 或 i - m - 1。

面试视角：面试官期待的就是这份 $O(n)$ 定长窗口。写完后主动指出「每次比较是 $O(26)$，可以进一步用一个 diff 计数器记录『有多少种字符的频次尚不匹配』，把比较降到 $O(1)$」是明确的加分项；被追问「字符集不是小写字母怎么办」，回答是换成哈希表并同时维护匹配种类数，思路不变。

易错点总结

错误写法：漏掉 m > n 的前置判断。输入 s1 = "abc"、s2 = "ab" 时建初始窗口就会访问 s2.charAt(2)，直接下标越界。

错误写法：建完初始窗口不比较，直接进入滑动循环。输入 s1 = "ab"、s2 = "ab" 时循环一次都不进，返回 false 而不是 true。

错误写法：移出的下标写成 i - m + 1。窗口左端多留了一个字符，输入 s1 = "ab"、s2 = "eidbaooo" 会因为计数永远对不上而返回 false。

错误写法：先比较再做两次计数更新。比较时窗口长度还是上一轮的状态，等价于整体延迟一格，输入 s1 = "ab"、s2 = "eidba" 会漏掉末尾的命中。

错误写法：只加不减（漏掉 --cnt2[...]）。cnt2 变成了前缀计数而非窗口计数，输入 s1 = "ab"、s2 = "cab" 时 cnt2 变成整段前缀的计数 {c:1, a:1, b:1}，与 cnt1 永远对不上，返回 false 而不是 true。

错误写法：Java 里用 cnt1 == cnt2 比较两个 int[]。比的是引用地址，恒为 false，任何输入都返回 false；Java 必须用 Arrays.equals。

错误写法：Go 里把计数容器声明成切片 make([]int, 26) 并用 == 比较。切片不可比较，直接编译报错；要么改用定长数组 [26]int，要么逐位比较。

错误写法：每个窗口都用 s2.substring(i, i + m) 取出子串再排序比较。逻辑对但每步 $O(m \log m)$，且不断创建新字符串，$10^4$ 规模下会明显超时。

错误写法：只比较窗口内字符的种类集合而不比较次数。输入 s1 = "aab"、s2 = "abb" 会被误判为 true，正确答案是 false。

相似题目

题目	难度	考察点
567. 字符串的排列	中等	与本题同题，可直接套用同一份定长窗口
438. 找到字符串中所有字母异位词	中等	求全部起点而非存在性，命中后不能提前返回，要继续滑完
LCR 015. 找到字符串中所有字母异位词	中等	与 438 同题，是「返回布尔」与「收集下标」这一差别的直接对照
76. 最小覆盖子串	困难	窗口长度可变，只需覆盖而非精确相等，要在收缩中求最短
3. 无重复字符的最长子串	中等	同为字符窗口但求最长，收缩条件是出现重复字符
30. 串联所有单词的子串	困难	把「字符」换成「等长单词」，需按单词长度分组做多条并行窗口