景真

外观

最小覆盖子串

约 965 字大约 3 分钟

滑动窗口

2025-02-25

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 <= 10^5
  • s 和 t 由英文字母组成

滑动窗口，哈希表

哈希表 need 存需要的字符及次数，哈希表 window 存窗口中的字符及次数，变量 valid 存已覆盖完成的字符的种类数。可以把哈希表换成英文字母数组。

class Solution {
    public String minWindow(String s, String t) {
        // need存需要的字符及次数
        Map<Character, Integer> need = new HashMap<>();
        // window存窗口中的字符及次数
        Map<Character, Integer> window = new HashMap<>();
        
        // 初始化need
        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }

        int left = 0;
        int right = 0;
        // valid存已覆盖完成的字符的种类数
        int valid = 0;
        // 记录答案——最小覆盖子串的起始索引及长度
        int start = 0;
        int len = Integer.MAX_VALUE;

        while (right < s.length()) {
            // c 是将移入窗口的字符
            char c = s.charAt(right);
            // 右移窗口
            right++;
            // 进行窗口内数据的一系列更新
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                // 一定不要用 ==！要用 equals！
                if (window.get(c).equals(need.get(c))) {
                    valid++;
                }
            }

            // 判断左侧窗口是否要收缩，覆盖够了就收缩，不然就多了，我们要求的是最短的满足条件的子串，所以取最小值的代码要放在while里，
            // 不能像3.无重复字符的最长子串那样在while外面
            while (valid == need.size()) {
                // 在这里更新最小覆盖子串
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }
                
                // d 是将移出窗口的字符
                char d = s.charAt(left);
                // 左移窗口
                left++;
                // 进行窗口内数据的一系列更新
                if (need.containsKey(d)) {
                    // 一定不要用 ==！要用 equals！
                    if (window.get(d).equals(need.get(d))) {
                        valid--;
                    }
                    window.put(d, window.get(d) - 1);
                }
            }
        }
        // 返回最小覆盖子串
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }
}

外层 while 循环的执行次数是 right 从 0 到 s.length()，所以执行次数是 O(|s|)。

内层 while 循环在每次外层循环中，可能最多执行 s.length() 次，但它实际上是随着 left 指针的移动从而缩小窗口。 因此，left 和 right 每个指针各自最多只会遍历一次字符串 s，使得总的遍历次数为 O(|s|)。

在每次移动窗口时，我们对哈希表进行插入、删除和查找操作。每个操作的时间复杂度是 O(1)， 但在最坏情况下，我们需要遍历哈希表need来检查 valid 是否等于 need.size()。这个操作的时间复杂度是 O(C)，其中 C 是字符集的大小。

初始化 need 哈希表的时间复杂度是 O(|t|)。

因此，总的时间复杂度是：

O(C⋅∣s∣+∣t∣)O(C \cdot |s| + |t|)

  • 空间复杂度：这里用了两张哈希表作为辅助空间，每张哈希表最多不会存放超过字符集大小的键値对，我们设字符集大小为 CC ，则浙进空间复杂度为 O(C)O(C) 。