会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员，或
购买
该题目所属题库
，可解锁完整内容。
解题思路
本题是经典的“最小覆盖子串”问题，适用 滑动窗口 + 计数 的思想。核心做法如下：
- 用一个长度为 128 的整型数组
need 统计字符串 t 中每个字符需要的数量（只含英文字母，用 ASCII 足够）。
- 维护双指针
[left, right] 表示当前窗口，并维护变量 missing 表示还缺多少个字符（按出现次数计），初始为 |t|。
- 向右移动
right 扩张窗口：将 s[right] 对应的 need 计数减一；若减完后该字符的 need 仍 ≥ 0，说明它满足了 t 的部分需求，missing--。
- 当
missing == 0 时，说明当前窗口已经覆盖了 t 的所有字符，此时尝试收缩左端 left，在仍满足覆盖条件下尽量缩短长度，并记录当前最短答案。一旦收缩到去掉 s[left] 会使 need[s[left]] > 0，表明覆盖被破坏，停止收缩并继续扩张右端。
- 扫描结束后，若记录过答案则输出最短子串，否则输出空串。
P3903.最小覆盖子串
题目内容
给定字符串 s 与字符串 t，请在 s 中找出包含 t 中所有字符(含出现次数) 的最短子串并输出该子串。
若 s 中不存在这样的子串，输出空字符串 ""（不带引号）。
注：对 t 中重复字符，子串中对应字符的数量必须不少于 t 中该字符的数量。若存在解，保证答案唯一。
输入描述
输出描述
- 一行：最短覆盖子串；若不存在则输出空字符串
""，不包含引号。
样例一
输入：
ADOBECODEBANC
ABC
输出：
BANC
样例二
输入：
a
a
输出：
a
样例三
输入：
a
aa
输出：
数据范围
- 1≤∣s∣,∣t∣≤105
s与t由英文字母组成
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
