题目

思路

一句话本质

用一张「需求表」记录 t 还缺哪些字符、各缺多少次；右指针扩张让窗口达标，左指针收缩让窗口最短，再用「已满足的字符种类数」判断是否覆盖。

最直白的做法：枚举所有子串

枚举 s 的所有左右端点，得到每个子串后，再逐个统计它是否覆盖 t。如果每次重新扫描，时间复杂度是 O(m³)；即使优化成边枚举边计数，也要 O(m²)。当 m = 10⁵ 时，O(m²) 已经到达 10¹⁰ 级别，明显不可行。

关键观察：覆盖性随窗口移动是单调的

当右端点向右移动时，窗口只会变长，覆盖能力只会增强或不变；当左端点向右移动时，窗口只会变短，覆盖能力只会减弱或不变。因此：

• 某个右端点一旦让窗口「刚好覆盖」，左端点就可以一路右移，直到窗口「差一点就不覆盖」。
• 右端点不需要回退：更靠右的答案只需要继续扩展新的右端点，再配合左端点收缩即可。

选定做法

采用「滑动窗口 + 需求表」。一个右指针只负责扩展，一个左指针只负责收缩；用 matched 表示「t 中已经满足频次要求的字符种类数」，当 matched 等于 t 中不同字符的总数时，当前窗口就是合法的。

解法

🔒

本篇为付费内容

您已阅读试读部分，购买后即可解锁全文。

⚠️ 本站内容已做唯一性标记并受版权保护，未经授权禁止转载，侵权必究。