题解 | 最小覆盖子串

1、解题思路

滑动窗口法：使用双指针（left 和 right）表示当前窗口的左右边界。扩展 right 指针，直到窗口包含 t 中的所有字符。收缩 left 指针，尽可能缩小窗口，同时保持窗口包含 t 中的所有字符。记录满足条件的最短子串。
哈希表辅助：使用哈希表记录 t 中每个字符的出现次数。在滑动窗口过程中，维护另一个哈希表，记录当前窗口中各字符的出现次数。判断当前窗口是否满足包含 t 中所有字符的条件。

2、代码实现

C++

#include <climits>
#include <unordered_map>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param S string字符串
     * @param T string字符串
     * @return string字符串
     */
    string minWindow(string S, string T) {
        // write code here
        unordered_map<char, int> target;    // 统计 T 中各字符出现的次数
        for (char c : T) {
            target[c]++;
        }

        int left = 0, right = 0;
        int min_len = INT_MAX;
        int min_left = 0;
        int required = target.size();   // 需要满足的字符种类
        int formed = 0; // 当前窗口中满足的字符种类数
        unordered_map<char, int> window;    // 统计当前窗口中各字符的出现次数

        while (right < S.size()) {
            char c = S[right];
            window[c]++;
            if (target.count(c) && window[c] == target[c]) {
                formed++;
            }

            // 尝试收缩窗口
            while (left <= right && formed == required) {
                // 更新最小窗口
                if (right - left + 1 < min_len) {
                    min_len = right - left + 1;
                    min_left = left;
                }

                // 移动左边界
                char left_char = S[left];
                window[left_char]--;
                if (target.count(left_char) && window[left_char] < target[left_char]) {
                    formed--;
                }
                left++;
            }
            right++;
        }
        return min_len == INT_MAX ? "" : S.substr(min_left, min_len);
    }
};

Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param S string字符串 
     * @param T string字符串 
     * @return string字符串
     */
    public String minWindow (String S, String T) {
        // write code here
        Map<Character, Integer> target = new HashMap<>();
        for (char c : T.toCharArray()) {
            target.put(c, target.getOrDefault(c, 0) + 1);
        }

        int left = 0, right = 0;
        int minLen = Integer.MAX_VALUE;
        int minLeft = 0;
        int required = target.size();
        int formed = 0;
        Map<Character, Integer> window = new HashMap<>();

        while (right < S.length()) {
            char c = S.charAt(right);
            window.put(c, window.getOrDefault(c, 0) + 1);
            if (target.containsKey(c) && window.get(c).equals(target.get(c))) {
                formed++;
            }

            while (left <= right && formed == required) {
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    minLeft = left;
                }

                char leftChar = S.charAt(left);
                window.put(leftChar, window.get(leftChar) - 1);
                if (target.containsKey(leftChar) && window.get(leftChar) < target.get(leftChar)) {
                    formed--;
                }
                left++;
            }

            right++;
        }

        return minLen == Integer.MAX_VALUE ? "" : S.substring(minLeft, minLeft + minLen);
    }
}

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param S string字符串 
# @param T string字符串 
# @return string字符串
#
from collections import defaultdict

class Solution:
    def minWindow(self , S: str, T: str) -> str:
        # write code here
        target = defaultdict(int)
        for c in T:
            target[c] += 1

        left = 0
        min_len = float('inf')
        min_left = 0
        required = len(target)
        formed = 0
        window = defaultdict(int)

        for right, c in enumerate(S):
            window[c] += 1
            if c in target and window[c] == target[c]:
                formed += 1

            while left <= right and formed == required:
                if right - left + 1 < min_len:
                    min_len = right - left + 1
                    min_left = left

                left_char = S[left]
                window[left_char] -= 1
                if left_char in target and window[left_char] < target[left_char]:
                    formed -= 1
                left += 1

        return "" if min_len == float('inf') else S[min_left:min_left + min_len]

3、复杂度分析

滑动窗口法：通过双指针动态调整窗口大小，确保窗口始终包含 t 中的所有字符。
哈希表辅助：使用哈希表统计 t 中字符的出现次数，并在滑动窗口中维护当前窗口的字符统计。
时间复杂度：滑动窗口遍历字符串 s 一次，时间复杂度为O(n)。
空间复杂度：使用哈希表存储字符统计，空间复杂度为O(n)。