题解

本题使用 滑动窗口 + 哈希表 进行求解。

解题思路

1. 定义哈希表

   • need: 存储 t 中各字符的需求数量。
   • window: 记录当前窗口内字符的出现次数。

2. 扩展窗口

   • 使用双指针 left 和 right，初始时 left=0, right=0。
   • 右指针 right 右移，扩展窗口，并更新 window。
   • 维护变量 valid，表示窗口中满足 t 要求的字符种类数。

3. 收缩窗口

   • 当 valid 等于 need.size()（即窗口已包含 t 中所有字符）：
     • 记录当前最短子串的起始位置 start 和长度 min_length。
     • 左指针 left 右移，缩小窗口，继续寻找最短覆盖子串。

4. 返回结果

   • 若找到有效子串，返回 s[start:start+min_length]。
   • 否则返回 ""。

复杂度分析

• 时间复杂度：( O(m + n) )（遍历 s 一次，每个字符最多进出窗口一次）。
• 空间复杂度：( O(1) )（哈希表存储字符，最多 26 个字母）。

代码实现

C++ 实现

#include<bits/stdc++.h>
using namespace std;

string minWindow(string s, string t) {
    unordered_map<char, int> need, window;
    
    // 统计 t 中字符的频率
    for (char c : t) need[c]++;
    
    int left = 0, right = 0, valid = 0;
    int start = 0, min_length = INT_MAX;

    while (right < s.size()) {
        char c = s[right];  // 即将进入窗口的字符
        right++;  // 扩展窗口

        // 只有 t 中包含该字符时才更新 window
        if (need.count(c)) {
            window[c]++;
            if (window[c] == need[c]) valid++;  // 当字符频率匹配时，valid 增加
        }

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

            char d = s[left];  // 即将移出窗口的字符
            left++;  // 缩小窗口

            // 只有 t 中包含该字符时才更新 window
            if (need.count(d)) {
                if (window[d] == need[d]) valid--;  // 失去一个满足的字符
                window[d]--;
            }
        }
    }

    return min_length == INT_MAX ? "" : s.substr(start, min_length);
}

int main() {
    string s, t;
    cin >> s >> t;  // 读取输入
    cout << minWindow(s, t) << endl;  // 输出结果
    return 0;
}

Python 实现

def min_window(s: str, t: str) -> str:
    from collections import Counter

    need = Counter(t)  # 统计 t 中字符的需求数量
    window = {}  # 记录窗口内字符的频率
    left = right = valid = 0
    start, min_length = 0, float('inf')

    while right < len(s):
        c = s[right]  # 即将进入窗口的字符
        right += 1  # 扩展窗口

        if c in need:
            window[c] = window.get(c, 0) + 1
            if window[c] == need[c]:  # 当字符频率匹配时，valid 增加
                valid += 1

        # 当窗口满足条件时，尝试收缩窗口
        while valid == len(need):
            # 更新最小覆盖子串
            if right - left < min_length:
                start, min_length = left, right - left

            d = s[left]  # 即将移出窗口的字符
            left += 1  # 缩小窗口

            if d in need:
                if window[d] == need[d]:  # 失去一个满足的字符
                    valid -= 1
                window[d] -= 1

    return "" if min_length == float('inf') else s[start:start + min_length]


if __name__ == "__main__":
    s = input().strip()
    t = input().strip()
    print(min_window(s, t))

Java 实现

import java.util.HashMap;
import java.util.Scanner;

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

        // 统计 t 中字符的需求数量
        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }

        int left = 0, right = 0, valid = 0;
        int start = 0, min_length = Integer.MAX_VALUE;

        while (right < s.length()) {
            char c = s.charAt(right);  // 即将进入窗口的字符
            right++;  // 扩展窗口

            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (window.get(c).equals(need.get(c))) valid++;  // 频率匹配时，valid++
            }

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

                char d = s.charAt(left);  // 即将移出窗口的字符
                left++;  // 缩小窗口

                if (need.containsKey(d)) {
                    if (window.get(d).equals(need.get(d))) valid--;  // 失去一个满足的字符
                    window.put(d, window.get(d) - 1);
                }
            }
        }

        return min_length == Integer.MAX_VALUE ? "" : s.substring(start, start + min_length);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.next();  // 读取输入
        String t = scanner.next();
        scanner.close();

        System.out.println(minWindow(s, t));  // 输出结果
    }
}

Leetcode 12.最小覆盖子串-原题链接

题目内容

给定字符串 s 与字符串 t，请在 s 中找出包含 t 中所有字符(含出现次数) 的最短子串并输出该子串。 若 s 中不存在这样的子串，输出空字符串 ""（不带引号）。

注：对 t 中重复字符，子串中对应字符的数量必须不少于 t 中该字符的数量。若存在解，保证答案唯一。

输入描述

• 第一行：字符串 s
• 第二行：字符串 t

输出描述

• 一行：最短覆盖子串；若不存在则输出空字符串 ""。

样例一

输入：

ADOBECODEBANC
ABC

输出：

BANC

样例二

输入：

a
a

输出：

a

样例三

输入：

a
aa

输出：

""

数据范围

• 1 ≤ |s|, |t| ≤ 10^5
• s与t由英文字母组成