最小覆盖子串（Minimum Window Substring） 题目描述 给定一个字符串 s 和一个字符串 t ，请你找出 s 中包含 t 所有字符（包括字符出现次数）的最小子串。如果 s 中不存在这样的子串，返回空字符串 "" 。 示例 输入： s = "ADOBECODEBANC" , t = "ABC" 输出： "BANC" 解释：最小子串 "BANC" 包含 'A', 'B', 'C' 各一个（来自 t 的字符和出现次数）。 解题思路 这个问题可以使用 滑动窗口 结合 线性动态规划思想 （通过维护计数状态）来解决。核心是：用两个指针（ left 和 right ）在 s 上定义一个窗口，移动指针来动态调整窗口，并实时检查当前窗口是否覆盖了 t 的所有字符。 具体步骤 统计字符需求 用一个哈希表（或长度为 128 的数组，覆盖 ASCII 码） need 记录 t 中每个字符需要的数量。例如 t = "ABC" ，则 need['A'] = 1, need['B'] = 1, need['C'] = 1 。 定义一个变量 needCount 表示总共还需要匹配的字符数量，初始为 t 的长度。 滑动窗口扫描 初始化 left = 0 , right = 0 ，以及记录最小窗口的起始位置 start 和长度 minLen （初始为无穷大）。 移动右指针 right ，扩大窗口： 对每个 s[right] ，如果它在 need 中的需求数大于 0，说明当前字符是 t 中需要的，将 needCount 减 1。 然后将 need[s[right]] 减 1（表示窗口中这个字符多覆盖了一个，可能为负，表示窗口中这个字符有多余）。 当 needCount == 0 时，表示当前窗口已覆盖 t 的所有字符，尝试收缩左指针以找到更小的窗口： 如果当前窗口长度 right - left + 1 小于 minLen ，更新 minLen 和 start = left 。 然后将 s[left] 移出窗口：如果 need[s[left]] == 0 ，说明移出的字符正好是所需字符，不再覆盖，因此 needCount 加 1。 无论是否所需，都将 need[s[left]] 加 1（恢复需求计数）。 左指针右移一位。 重复直到 right 扫描完整个字符串。 结果输出 如果 minLen 仍然是无穷大，返回 "" 。 否则返回 s[start:start+minLen] 。 示例模拟 以 s = "ADOBECODEBANC" , t = "ABC" 为例： 初始化： need = {'A':1, 'B':1, 'C':1} , needCount = 3 , left=0, right=0 , minLen = ∞ 。 移动右指针到 0（'A'）： need['A'] 减 1 变成 0， needCount 减 1 变成 2。 继续右移，到 5（'C'）时，窗口 "ADOBEC" 覆盖了所有字符（ needCount=0 ），记录窗口长度 6，收缩左指针。 移动左指针直到窗口不再覆盖（ needCount > 0 ），再移动右指针寻找下一个覆盖窗口。最终在右指针到 12 时，左指针收缩到 9，得到更小窗口 "BANC" 长度 4。 最终结果 "BANC"。 复杂度分析 时间复杂度：O(|s| + |t|)，每个字符最多进入和离开窗口一次。 空间复杂度：O(|字符集|)，用于存储 need 数组。 扩展思考 如果 t 中可能包含重复字符，本方法已通过计数处理。 如果要求子串中字符顺序必须与 t 一致，则问题会变得更复杂（需结合序列匹配 DP）。 这个解法巧妙地用滑动窗口动态维护覆盖状态，并通过 needCount 避免每次检查窗口都要遍历哈希表，是线性动态规划中“状态压缩”思想的典型应用。