P3259. 最左侧冗余覆盖子串

解题思路

本题是 经典题型、最小覆盖子串 的 固定滑窗 版本，直接使用 三问三答 即可解决。

在代码层面，本题和 【固定滑窗】2024E-关联字串 非常相似，可以放在一起进行比较。

区别在于

• 固定滑窗的长度 win_len 从 n1 修改为 n1 + k，表示窗口长度包含长度 k 的冗余。
• `check()` 函数 的 == 修改为 <=，表示 s2 的子串需要 覆盖 s1，而非和 s1 的排列全等。

剩下的内容几乎和 【固定滑窗】2025B-关联字串 完全相同。

思路展开

• 代码里的固定窗口长度取 win_len = n1 + k：题目要求子串长度恰好为 n1 + k，所以只需在 s2 上枚举所有这个长度的连续子串即可。
• ans_cnt 用 Counter 统计 s1 中每个字母的出现次数，代表「需要被覆盖的需求」；win_cnt 统计当前窗口内每个字母的出现次数，代表「窗口能提供的供给」。
• check 函数逐一检查 ans_cnt 中每个字母的次数是否都不超过 win_cnt 中对应字母的次数，全部满足就说明窗口包含了 s1 的所有字母、且每个字母的次数都不少于 s1，即构成一次冗余覆盖。这里用 <= 而不是 ==，因为窗口比 s1 长 k，多出来的字符是题目允许的冗余部分。
• 主流程先单独判断第一个窗口（左端点下标 0）；之后右指针 right 从 win_len 开始右移，每步把新字符计入 win_cnt、把滑出窗口的 s2[right - win_len] 从 win_cnt 中减掉，使 win_cnt 始终精确对应当前窗口的内容。
• 每滑一步就 check 一次，第一次通过时当前窗口的左端点为 right - win_len + 1，记入 ans 并立刻 break。由于枚举是从左到右进行的，第一次命中的必然是最左侧的合法子串；若扫到结尾都不满足，ans 保持初始值 -1。

复杂度分析 设 n1、n2 为 s1、s2 的长度，C 为 s1 中不同字符的个数（字符集大小，常数级别）。

• 时间复杂度：O(n1 + k + n2 × C)。建立 ans_cnt 遍历 s1 是 O(n1)，初始化第一个窗口遍历 s2 的前 n1 + k 个字符是 O(n1 + k)；滑窗阶段右指针最多走 n2 - win_len 步，每步计数更新为 O(1)，而 check 要对 ans_cnt 的每个键比对一次，为 O(C)，所以这一段最坏是 O(n2 × C)。字符集为常数时整体就是线性 O(n1 + n2)。
• 空间复杂度：O(C)。两个计数器只按字符种类存键，与字符串长度无关。