代码随想录

# 76. 最小覆盖子串

力扣题目链接 (opens new window)

给你一个字符串 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"

示例 3：

输入：s = "a", t = "aa"

输出：""

解释：t 中两个字符 'a' 均应包含在 s 的子串中，因此没有符合条件的子串，返回空字符串。

提示：

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

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

# 思路

# 暴力解法

这道题最直观的思路是什么？暴力！

枚举 s 的所有子串，判断子串是否覆盖了 t 的所有字符（含重复），在所有满足条件的子串中找最短的。

时间复杂度 O(n^2 × m)，其中 n 是 s 的长度，m 是 t 的长度。这个复杂度显然太高了，会超时。

# 滑动窗口

这道题是经典的滑动窗口问题，和之前做过的 209.长度最小的子数组 (opens new window) 思路非常类似，只不过那道题是求和满足条件，这道题是字符覆盖满足条件。

滑动窗口的核心思想就是：

  1. right 指针不断右移，扩大窗口，直到窗口内的内容满足了要求（覆盖了 t 的所有字符）
  2. left 指针不断右移，缩小窗口，直到窗口内的内容不再满足要求
  3. 在这个过程中，记录所有满足条件的最小窗口

我们来看一下滑动窗口的原理图：

如图所示，滑动窗口就是不断「扩大 → 缩小 → 扩大 → 缩小」的过程，在满足条件的窗口中找最小的那个。

# 关键问题

但是这道题的难点在于：如何判断窗口是否覆盖了 t 的所有字符？

t 中可能有重复字符，比如 t = "AABC"，那窗口中必须至少有 2 个 A、1 个 B、1 个 C 才算覆盖。

这时候就需要用到哈希表来统计字符的需求数量。

我们定义两个哈希表：

  • need：记录 t 中每个字符需要的数量
  • window：记录当前窗口中每个字符的数量

另外，我们可以用一个变量 count 来记录当前窗口中已经满足需求的字符种类数（不是字符个数）。当 count == need.size() 时，说明窗口已经覆盖了 t 的所有字符。

为什么用"已满足的字符种类数"而不是"已满足的字符个数"？

因为 t 中可能有重复字符，比如 t = "AAB"，need 的大小是 2（A 和 B 两种），不是 3。我们只需要关心每种字符是否满足需求，而不需要关心总共有多少个字符。

# 算法流程

结合上面的分析，完整的滑动窗口算法流程如下：

  1. 用 need 哈希表统计 t 中每个字符的出现次数
  2. 初始化 left = 0, right = 0, count = 0
  3. right 不断右移：
    • 如果 s[right] 是 t 中的字符，更新 window，如果该字符数量刚好满足需求，count++
    • 当 count == need.size() 时，尝试收缩窗口
  4. left 不断右移收缩窗口：
    • 如果 s[left] 是 t 中的字符，更新 window，如果该字符数量不够了，count--
    • 更新最小窗口的起始位置和长度
  5. 重复 3-4 直到 right 遍历完 s

让我们用题目示例 s = "ADOBECODEBANC", t = "ABC" 来一步步模拟：

从图中可以清楚看到整个滑动窗口的移动过程：

  1. right 从 0 移到 5，窗口 [ADOBEC] 第一次满足条件，长度 6
  2. left 右移缩小窗口，移除 A 后不再满足条件
  3. right 继续右移到 10，窗口 [BECODEBA] 再次满足条件，但长度 8 大于之前的 6
  4. left 右移缩小窗口，移除 B、E、C 后不再满足
  5. right 继续右移到 12，窗口包含 ABC，left 右移缩小后得到 [BANC]，长度 4
  6. 最终结果为 "BANC"

# 代码实现

有了上面的分析，代码就不难写了。

C++代码如下：

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> need, window;
        for (char c : t) need[c]++;

        int left = 0, right = 0;
        int count = 0; // 记录窗口中满足need要求的字符种类数
        int start = 0, minLen = INT_MAX; // 记录最小窗口的起始位置和长度

        while (right < s.size()) {
            char c = s[right];
            right++;
            // 如果是t中的字符，更新window
            if (need.count(c)) {
                window[c]++;
                // 字符c的数量刚好满足需求，count++
                if (window[c] == need[c]) {
                    count++;
                }
            }

            // 当窗口满足条件时，尝试收缩
            while (count == need.size()) {
                // 更新最小窗口
                if (right - left < minLen) {
                    start = left;
                    minLen = right - left;
                }

                char d = s[left];
                left++;
                // 如果移除的是t中的字符，更新window
                if (need.count(d)) {
                    // 字符d的数量不再满足需求，count--
                    if (window[d] == need[d]) {
                        count--;
                    }
                    window[d]--;
                }
            }
        }

        return minLen == INT_MAX ? "" : s.substr(start, minLen);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
  • 时间复杂度: O(m + n)，其中 m 是 s 的长度，n 是 t 的长度。left 和 right 指针各自最多遍历 s 一次。
  • 空间复杂度: O(k)，k 是字符集的大小，这里是英文字母，最多 52 个。

# 代码详解

我们来仔细分析一下代码中的几个关键点：

1. 什么时候 count++？

if (window[c] == need[c]) {
    count++;
}
1
2
3

只有当字符 c 在窗口中的数量刚好等于需求时，count 才增加。如果 window[c] 已经大于 need[c]，说明之前已经满足过了，不需要重复计数。

2. 什么时候 count--？

if (window[d] == need[d]) {
    count--;
}
1
2
3

只有当字符 d 在窗口中的数量刚好等于需求时，移除它才会导致不满足。如果 window[d] 已经大于 need[d]，移除一个仍然满足需求。

3. 为什么要先判断再减？

注意收缩窗口时的判断顺序：先判断 window[d] == need[d]，再执行 window[d]--。因为如果先减再判断，就无法知道减之前是否刚好满足需求了。

4. 内层 while 还是 if？

很多录友们可能会问，为什么内层用 while 而不是 if？

因为一次收缩可能不够。比如 s = "AAAABC", t = "ABC"，当 right 到达 C 时窗口满足条件，但 left 需要跳过前面多余的 A 才能找到最小窗口。用 while 可以持续收缩直到窗口不再满足条件。

# 扩展

# 滑动窗口模板

这道题的代码结构其实是一个通用的滑动窗口模板，适用于很多子串/子数组问题：

// 滑动窗口模板
int left = 0, right = 0;
while (right < s.size()) {
    // 扩大窗口
    window.add(s[right]);
    right++;

    while (窗口满足条件) {
        // 更新结果
        ...

        // 缩小窗口
        window.remove(s[left]);
        left++;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

大家可以把 209.长度最小的子数组 (opens new window)、904.水果成篮 (opens new window) 这些题也用这个模板写一下，体会一下滑动窗口的通用性。

# 字符频数用数组代替哈希表

如果题目明确字符集的范围（比如只有大小写英文字母），可以用数组代替哈希表来提升性能，因为数组的访问是 O(1) 常数时间，比哈希表更稳定。

int need[128] = {0};  // ASCII字符集
int window[128] = {0};
1
2

这个优化在实际提交中可以将运行时间提升 30%~50%，感兴趣的录友们可以自己尝试。

# 其他语言版本

# Java：

class Solution {
    public String minWindow(String s, String t) {
        HashMap<Character, Integer> need = new HashMap<>();
        HashMap<Character, Integer> window = new HashMap<>();

        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }

        int left = 0, right = 0;
        int count = 0; // 记录窗口中满足need要求的字符种类数
        int start = 0, minLen = Integer.MAX_VALUE; // 记录最小窗口的起始位置和长度

        while (right < s.length()) {
            char c = s.charAt(right);
            right++;
            // 如果是t中的字符，更新window
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                // 字符c的数量刚好满足需求，count++
                if (window.get(c).equals(need.get(c))) {
                    count++;
                }
            }

            // 当窗口满足条件时，尝试收缩
            while (count == need.size()) {
                // 更新最小窗口
                if (right - left < minLen) {
                    start = left;
                    minLen = right - left;
                }

                char d = s.charAt(left);
                left++;
                // 如果移除的是t中的字符，更新window
                if (need.containsKey(d)) {
                    // 字符d的数量不再满足需求，count--
                    if (window.get(d).equals(need.get(d))) {
                        count--;
                    }
                    window.put(d, window.get(d) - 1);
                }
            }
        }

        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

# Python：

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        from collections import defaultdict

        need = defaultdict(int)
        window = defaultdict(int)
        for c in t:
            need[c] += 1

        left = 0
        count = 0  # 记录窗口中满足need要求的字符种类数
        start = 0
        minLen = float('inf')  # 记录最小窗口的起始位置和长度

        for right, c in enumerate(s):
            # 如果是t中的字符，更新window
            if c in need:
                window[c] += 1
                # 字符c的数量刚好满足需求，count++
                if window[c] == need[c]:
                    count += 1

            # 当窗口满足条件时，尝试收缩
            while count == len(need):
                # 更新最小窗口
                if right - left + 1 < minLen:
                    start = left
                    minLen = right - left + 1

                d = s[left]
                left += 1
                # 如果移除的是t中的字符，更新window
                if d in need:
                    # 字符d的数量不再满足需求，count--
                    if window[d] == need[d]:
                        count -= 1
                    window[d] -= 1

        return "" if minLen == float('inf') else s[start:start + minLen]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

# Go：

func minWindow(s string, t string) string {
    need := make(map[byte]int)
    window := make(map[byte]int)
    for i := 0; i < len(t); i++ {
        need[t[i]]++
    }

    left, count := 0, 0  // count记录窗口中满足need要求的字符种类数
    start, minLen := 0, len(s)+1  // 记录最小窗口的起始位置和长度

    for right := 0; right < len(s); right++ {
        c := s[right]
        // 如果是t中的字符，更新window
        if _, ok := need[c]; ok {
            window[c]++
            // 字符c的数量刚好满足需求，count++
            if window[c] == need[c] {
                count++
            }
        }

        // 当窗口满足条件时，尝试收缩
        for count == len(need) {
            // 更新最小窗口
            if right-left+1 < minLen {
                start = left
                minLen = right - left + 1
            }

            d := s[left]
            left++
            // 如果移除的是t中的字符，更新window
            if _, ok := need[d]; ok {
                // 字符d的数量不再满足需求，count--
                if window[d] == need[d] {
                    count--
                }
                window[d]--
            }
        }
    }

    if minLen == len(s)+1 {
        return ""
    }
    return s[start : start+minLen]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

# JavaScript：

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function(s, t) {
    const need = new Map();
    const window = new Map();
    for (const c of t) {
        need.set(c, (need.get(c) || 0) + 1);
    }

    let left = 0, count = 0;  // count记录窗口中满足need要求的字符种类数
    let start = 0, minLen = Infinity;  // 记录最小窗口的起始位置和长度

    for (let right = 0; right < s.length; right++) {
        const c = s[right];
        // 如果是t中的字符，更新window
        if (need.has(c)) {
            window.set(c, (window.get(c) || 0) + 1);
            // 字符c的数量刚好满足需求，count++
            if (window.get(c) === need.get(c)) {
                count++;
            }
        }

        // 当窗口满足条件时，尝试收缩
        while (count === need.size) {
            // 更新最小窗口
            if (right - left + 1 < minLen) {
                start = left;
                minLen = right - left + 1;
            }

            const d = s[left];
            left++;
            // 如果移除的是t中的字符，更新window
            if (need.has(d)) {
                // 字符d的数量不再满足需求，count--
                if (window.get(d) === need.get(d)) {
                    count--;
                }
                window.set(d, window.get(d) - 1);
            }
        }
    }

    return minLen === Infinity ? "" : s.substring(start, start + minLen);
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

# TypeScript：

function minWindow(s: string, t: string): string {
    const need: Map<string, number> = new Map();
    const window: Map<string, number> = new Map();
    for (const c of t) {
        need.set(c, (need.get(c) || 0) + 1);
    }

    let left: number = 0, count: number = 0;  // count记录窗口中满足need要求的字符种类数
    let start: number = 0, minLen: number = Infinity;  // 记录最小窗口的起始位置和长度

    for (let right = 0; right < s.length; right++) {
        const c: string = s[right];
        // 如果是t中的字符，更新window
        if (need.has(c)) {
            window.set(c, (window.get(c) || 0) + 1);
            // 字符c的数量刚好满足需求，count++
            if (window.get(c) === need.get(c)) {
                count++;
            }
        }

        // 当窗口满足条件时，尝试收缩
        while (count === need.size) {
            // 更新最小窗口
            if (right - left + 1 < minLen) {
                start = left;
                minLen = right - left + 1;
            }

            const d: string = s[left];
            left++;
            // 如果移除的是t中的字符，更新window
            if (need.has(d)) {
                // 字符d的数量不再满足需求，count--
                if (window.get(d) === need.get(d)) {
                    count--;
                }
                window.set(d, window.get(d)! - 1);
            }
        }
    }

    return minLen === Infinity ? "" : s.substring(start, start + minLen);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

# Rust：

use std::collections::HashMap;

impl Solution {
    pub fn min_window(s: String, t: String) -> String {
        let s: Vec<char> = s.chars().collect();
        let t: Vec<char> = t.chars().collect();

        let mut need: HashMap<char, i32> = HashMap::new();
        let mut window: HashMap<char, i32> = HashMap::new();

        for &c in &t {
            *need.entry(c).or_insert(0) += 1;
        }

        let mut left = 0;
        let mut count = 0;  // 记录窗口中满足need要求的字符种类数
        let mut start = 0;
        let mut min_len = usize::MAX;  // 记录最小窗口的起始位置和长度

        for right in 0..s.len() {
            let c = s[right];
            // 如果是t中的字符，更新window
            if let Some(&need_c) = need.get(&c) {
                *window.entry(c).or_insert(0) += 1;
                // 字符c的数量刚好满足需求，count++
                if window.get(&c).unwrap() == &need_c {
                    count += 1;
                }
            }

            // 当窗口满足条件时，尝试收缩
            while count == need.len() {
                // 更新最小窗口
                if right - left + 1 < min_len {
                    start = left;
                    min_len = right - left + 1;
                }

                let d = s[left];
                left += 1;
                // 如果移除的是t中的字符，更新window
                if let Some(&need_d) = need.get(&d) {
                    // 字符d的数量不再满足需求，count--
                    if window.get(&d).unwrap() == &need_d {
                        count -= 1;
                    }
                    *window.get_mut(&d).unwrap() -= 1;
                }
            }
        }

        if min_len == usize::MAX {
            String::new()
        } else {
            s[start..start + min_len].iter().collect()
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

# C：

char* minWindow(char* s, char* t) {
    int need[128] = {0};
    int window[128] = {0};
    int needCount = 0; // need中不同字符的种类数

    for (int i = 0; t[i]; i++) {
        if (need[t[i]] == 0) needCount++;
        need[t[i]]++;
    }

    int left = 0, count = 0;  // count记录窗口中满足need要求的字符种类数
    int start = 0, minLen = INT_MAX;  // 记录最小窗口的起始位置和长度
    int sLen = strlen(s);

    for (int right = 0; right < sLen; right++) {
        char c = s[right];
        // 如果是t中的字符，更新window
        if (need[c] > 0) {
            window[c]++;
            // 字符c的数量刚好满足需求，count++
            if (window[c] == need[c]) {
                count++;
            }
        }

        // 当窗口满足条件时，尝试收缩
        while (count == needCount) {
            // 更新最小窗口
            if (right - left + 1 < minLen) {
                start = left;
                minLen = right - left + 1;
            }

            char d = s[left];
            left++;
            // 如果移除的是t中的字符，更新window
            if (need[d] > 0) {
                // 字符d的数量不再满足需求，count--
                if (window[d] == need[d]) {
                    count--;
                }
                window[d]--;
            }
        }
    }

    if (minLen == INT_MAX) return "";

    char* result = (char*)malloc(sizeof(char) * (minLen + 1));
    strncpy(result, s + start, minLen);
    result[minLen] = '\0';
    return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
上次更新：: 4/22/2026, 9:10:06 AM

评论

验证登录状态...