LeetCode 567《字符串的排列》这道题是 “滑动窗口” (Sliding Window) 和 “哈希表/数组计数” (Hash/Array Counting) 的教科书级例题，非常适合用来训练优化 $O(N^2)$ 到 $O(N)$ 的思维。

---

第一部分：题目描述

题目名称： 字符串的排列 (Permutation in String) 输入文件： permutation.in 输出文件： permutation.out 时间限制： 1.0 s 空间限制： 256 MB

【题目描述】

给你两个字符串 $s_1$ 和 $s_2$。请你判断 $s_2$ 中是否存在一个子串，是 $s_1$ 的排列。

如果是，输出 true；否则，输出 false。

定义说明：

1. 排列 (Permutation)：是指由原字符串中的所有字符重新排列组合而成的新字符串（即字符出现的种类和次数完全相同，顺序可以不同）。
2. 子串 (Substring)：是字符串中连续的一段字符序列。

换句话说，你需要判断 $s_2$ 中是否包含一个连续的子串，该子串恰好包含了 $s_1$ 中的所有字符，且每个字符出现的频率与 $s_1$ 完全一致。

【输入格式】

输入文件包含两行： 第一行包含一个字符串 $s_1$。 第二行包含一个字符串 $s_2$。 两个字符串均只包含小写英文字母。

【输出格式】

输出一行字符串：如果存在符合条件的子串，输出 true，否则输出 false。

【输入样例 1】

ab
eidbaooo

【输出样例 1】

true

(说明：s2 包含 "ba"，它是 s1 "ab" 的排列)

【输入样例 2】

ab
eidboaoo

【输出样例 2】

false

(说明：虽然 s2 包含 'a' 和 'b'，但它们不是连续的，所以不构成子串)

【数据范围与提示】

• $1 \le |s_1|, |s_2| \le 10^4$
• 字符串仅包含小写英文字母 ('a'-'z')。

---

第二部分：教练辅导时间

1. 读题关键词 (Key Terms)

• “子串” $\rightarrow$ 连续的。这意味着我们不能跳着选字符。
• “排列” $\rightarrow$ 顺序不重要，数量最重要。只要字符的统计频次一样，就是排列。
• 隐含条件 $\rightarrow$ 我们要找的子串长度必须等于 $s_1$ 的长度。

2. 预备知识点 (Prerequisites)

• 哈希表/计数数组：用来统计字符出现的次数。因为只有 'a'-'z'，用 int cnt[26] 数组比 std::map 更快更省空间。
• 滑动窗口 (Sliding Window)：一种处理连续子数组/子串问题的核心技巧，能把嵌套循环的时间复杂度降下来。

3. 启发式教学与草稿纸推演 (Heuristic Approach)

来，拿出草稿纸，我们画图模拟一下滑动窗口的过程。

场景设置：

• $s_1 = \text{"ab"}$ (目标：找一个长度为2，包含1个a和1个b的子串)
• $s_2 = \text{"eidbaooo"}$

核心思想： 我们要维护一个长度固定为 $|s_1|$ (即 2) 的框，在 $s_2$ 上从左往右滑。每滑一格，看看框里的字符统计是否和 $s_1$ 一样。

推演步骤：

第一步：分析目标 $s_1$

• $s_1$ 统计：{a:1, b:1, 其他:0}
• 窗口长度 $L = 2$

第二步：开始滑动

步骤	窗口位置 (下标)	窗口内子串	窗口统计	目标统计	是否匹配?	操作
Init	[0, 1]	"ei"	e:1, i:1	a:1, b:1	否	窗口右移
Step 1	[1, 2]	"id"	进来 d，出去 e i:1, d:1
Step 2	[2, 3]	"db"	进来 b，出去 i d:1, b:1
Step 3	[3, 4]	"ba"	进来 a，出去 d b:1, a:1		是!	Return true

图形化思考（进出原则）： 想象一个框，向右移动一格时：

1. 吃进一个新的字符（右边的）。
2. 拉出一个旧的字符（左边的）。
3. 只需要更新这两个字符的计数，不需要重新遍历整个框！

4. 复杂度分析

• 暴力法：

  • 枚举 $s_2$ 的每一个起点 $i$。
  • 截取长度为 $L$ 的子串。
  • 排序子串和 $s_1$ 进行比较（或者统计计数）。
  • 时间复杂度：$O((N-M) \cdot M \log M)$ 或 $O((N-M) \cdot M)$，其中 $N=|s_2|, M=|s_1|$。如果 $M$ 很大，这会超时。

• 滑动窗口法 (优化后)：

  • 我们只遍历一次 $s_2$。
  • 每次窗口移动，只做常数次操作（加一个计数，减一个计数，比对一下26个字母的计数数组）。
  • 时间复杂度：$O(N + 26 \cdot (N-M))$，近似为 $O(N)$。
  • 空间复杂度：$O(1)$ (因为数组大小固定为 26，与输入规模无关)。

---

第三部分：标准题解代码 (NOI C++14)

/*
 * 题目：字符串的排列 (Permutation in String)
 * 来源：改编自 LeetCode 567
 * 算法：滑动窗口 + 数组哈希
 * 时间复杂度：O(N)，其中 N 为 s2 的长度
 * 空间复杂度：O(1)，常数级空间 (26个字母)
 */

#include <iostream>
#include <vector>
#include <string>

using namespace std;

// 辅助函数：判断两个频率数组是否完全相同
bool check(const vector<int>& cnt1, const vector<int>& cnt2) {
    for (int i = 0; i < 26; ++i) {
        if (cnt1[i] != cnt2[i]) return false;
    }
    return true;
}

int main() {
    // 【关键点1】I/O 加速
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s1, s2;
    if (!(cin >> s1 >> s2)) return 0;

    int n = s1.length();
    int m = s2.length();

    // 【边界处理】如果 s1 比 s2 长，s2 绝不可能包含 s1 的排列
    if (n > m) {
        cout << "false" << endl;
        return 0;
    }

    // 【数据结构】使用数组代替哈希表，统计 'a'-'z' 的频率
    // vector<int> 支持直接使用 == 运算符进行比较，
    // 但为了教学展示底层逻辑，这里展示手动比较或数组操作
    vector<int> cnt1(26, 0);
    vector<int> cnt2(26, 0);

    // 1. 统计 s1 的字符频率
    for (char c : s1) {
        cnt1[c - 'a']++;
    }

    // 2. 初始化第一个窗口 (长度为 n)
    // 先把 s2 的前 n 个字符读进窗口
    for (int i = 0; i < n; ++i) {
        cnt2[s2[i] - 'a']++;
    }

    // 检查第一个窗口是否匹配
    if (cnt1 == cnt2) {
        cout << "true" << endl;
        return 0;
    }

    // 3. 开始滑动窗口
    // 窗口范围：[left, right]
    // 初始时窗口是 [0, n-1]，现在我们要引入 s2[i]，扔掉 s2[i-n]
    for (int i = n; i < m; ++i) {
        // 【入窗口】：右边加入一个字符
        cnt2[s2[i] - 'a']++;
        
        // 【出窗口】：左边移除一个字符
        // 当前窗口长度原本是 n，加入 i 后变成 n+1，
        // 需要移除最左边的字符，即下标为 i-n 的字符
        cnt2[s2[i - n] - 'a']--;

        // 【检查匹配】
        // vector 重载了 == 运算符，会逐个比较元素，相当于 O(26)
        if (cnt1 == cnt2) {
            cout << "true" << endl;
            return 0;
        }
    }

    // 跑完了也没找到
    cout << "false" << endl;

    return 0;
}

易错点与进阶提示

1. 边界条件： 千万别忘了检查 s1.length() > s2.length() 的情况。如果不检查，后面的循环逻辑可能会导致数组越界或逻辑错误。
2. 字符映射： 使用 char - 'a' 将字符映射到 0-25 的数组下标是竞赛中最常用的技巧。
3. 常数优化： 代码中使用了 vector 的 == 运算符，这在 C++ 中是合法的且会逐元素比较。在极端卡常的题目中，可以用一个变量 diff 来记录当前窗口和目标有多少个字符数量不一致，从而避免每次都遍历 26 个位置，将复杂度严格降为 $O(N)$ 而不是 $O(26N)$。但对于本题 $10^4$ 的数据范围，$O(26N)$ 绰绰有余。

希望这份材料能帮助学生深刻理解滑动窗口的精髓！如果有问题，可以随时再让我在草稿纸上画一遍。