012.最小覆盖子串

76. 最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t
所有字符的子串，则返回空字符串 "" 。

注意：

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
• 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

示例 3:

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

提示：

• m == s.length
• n == t.length
• 1 <= m, n <= 105
• s 和 t 由英文字母组成

进阶：你能设计一个在 o(m+n) 时间内解决此问题的算法吗？

题解思路

这道题同样适用滑动窗口
思路，我们想要原始串中找到最小的子串可以覆盖目标串，我们可以先移动窗口的终止位置，直到找到一个覆盖目标串的子串后，再向右移动窗口的起始位置（缩小窗口的大小，看缩小后是否仍然满足覆盖目标串）。

这里需要注意的是，如何判断原始串是否覆盖目标串，我们先统计目标串需要各种字符个数， 统计原始串 i~j 范围各种字符个数
，如果在这个范围内，目标串需要的字符个数恰好等于原始串i~j 范围各种字符个数，则说明已经覆盖目标串。

解题步骤如下：

1. 统计目标串需要各种字符个数， 统计原始串 i~j 范围各种字符个数
2. 如果原始串 i~j 范围内不满足条件，j++ 扩大范围，直到满足条件 j 停下来
3. 一旦满足条件 i++ 缩小范围，直到再次不满足条件 …
4. 重复 2. 3. 两步直至 j 到达原始串末尾

图解步骤

题解代码

/**
 * @version v1.0
 * @author OldGj 2025/2/15
 * @apiNote 76. 最小覆盖子串
 */
public class _012_minWindow {
    /**
     * 封装窗口起始位置和终止位置的静态类
     * 在方法返回值时，可以使用起始位置和终止位置截取字符串进行返回
     */
    static class Result {
        int left;
        int right;

        public Result(Integer left, Integer right) {
            this.left = left;
            this.right = right;
        }
    }

    public String minWindow(String s, String t) {
        char[] sourceArr = s.toCharArray(); // 原始串
        int[] sourceCount = new int[128];

        char[] targetArr = t.toCharArray(); // 目标串
        int[] targetCount = new int[128];

        for (char c : targetArr) {
            targetCount[c]++; // 目标串中一个字符出现了几次
        }
        int count = 0; // 需要满足多少个条件
        for (int i : targetCount) {
            if (i > 0) { // 将一个字符看做一个条件，目标串中有多少种字符就有多少条件
                count++;
            }
        }

        int counted = 0;// 已经满足的条件
        int left = 0; // 滑动窗口的起始位置 left
        Result res = null;
        for (int right = 0; right < sourceArr.length; right++) { // 滑动窗口的终止位置right
            char rightCh = sourceArr[right];
            // 统计原始串 left~right 范围各种字符的个数
            sourceCount[rightCh]++;
            // 如果原始串中字符出现的次数等于目标串中字符出现的次数
            if (sourceCount[rightCh] == targetCount[rightCh]) {
                counted++; // 每满足一个条件，counted++
            }
            while (left <= right && counted == count) { // 当前窗口满足所有条件后，尝试缩小窗口
                // 找所有满足条件的解中，长度最小的
                if (res == null) {
                    res = new Result(left, right);
                } else {
                    if ((right - left) < (res.right - res.left)) {
                        res = new Result(left, right);
                    }
                }
                // 开始移动left，找长度更小的解
                char leftCh = sourceArr[left];
                sourceCount[leftCh]--;
                // 如果原始串中字符出现的次数小于了目标串中字符出现的此时，将counted--
                if (sourceCount[leftCh] < targetCount[leftCh]) {
                    counted--;
                }
                left++;
            }
        }
        return res == null ? "" : new String(sourceArr, res.left, res.right - res.left + 1);
    }
}