Hard

题目描述

给你一个字符串 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 的子串中，
因为 s 只有一个字符 'a'，所以无法满足条件，返回空字符串。

提示：

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

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

解题思路

这是一道经典的滑动窗口问题。核心思路是使用双指针技术维护一个可变大小的窗口。

算法思路

  1. 预处理目标字符串：统计字符串 t 中每个字符的出现次数
  2. 扩展右边界：移动右指针扩大窗口，直到窗口包含 t 中的所有字符
  3. 收缩左边界：当窗口满足条件时，尝试移动左指针缩小窗口，同时更新最小窗口记录
  4. 重复过程：继续移动右指针，重复上述过程直到遍历完整个字符串

关键技巧

  • 使用哈希表记录目标字符的需求量和当前窗口的字符统计
  • 用 valid 变量记录当前窗口中满足要求的字符种类数
  • 当 valid == need.size() 时，说明窗口已覆盖所有目标字符
  • 在满足条件的前提下尽可能缩小窗口来寻找最优解

这种方法的时间复杂度是 O(m+n)，其中每个字符最多被访问两次（左右指针各一次），空间复杂度为 O(k)，k 为字符集大小。

代码实现

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 valid = 0;
        int start = 0, len = INT_MAX;
        
        while (right < s.size()) {
            char c = s[right];
            right++;
            
            if (need.count(c)) {
                window[c]++;
                if (window[c] == need[c])
                    valid++;
            }
            
            while (valid == need.size()) {
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }
                
                char d = s[left];
                left++;
                
                if (need.count(d)) {
                    if (window[d] == need[d])
                        valid--;
                    window[d]--;
                }
            }
        }
        
        return len == INT_MAX ? "" : s.substr(start, len);
    }
};

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 = right = 0
        valid = 0
        start = 0
        length = float('inf')
        
        while right < len(s):
            c = s[right]
            right += 1
            
            if c in need:
                window[c] += 1
                if window[c] == need[c]:
                    valid += 1
            
            while valid == len(need):
                if right - left < length:
                    start = left
                    length = right - left
                
                d = s[left]
                left += 1
                
                if d in need:
                    if window[d] == need[d]:
                        valid -= 1
                    window[d] -= 1
        
        return "" if length == float('inf') else s[start:start + length]

public class Solution {
    public string MinWindow(string s, string t) {
        var need = new Dictionary<char, int>();
        var window = new Dictionary<char, int>();
        
        foreach (char c in t) {
            need[c] = need.ContainsKey(c) ? need[c] + 1 : 1;
        }
        
        int left = 0, right = 0;
        int valid = 0;
        int start = 0, len = int.MaxValue;
        
        while (right < s.Length) {
            char c = s[right];
            right++;
            
            if (need.ContainsKey(c)) {
                window[c] = window.ContainsKey(c) ? window[c] + 1 : 1;
                if (window[c] == need[c])
                    valid++;
            }
            
            while (valid == need.Count) {
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }
                
                char d = s[left];
                left++;
                
                if (need.ContainsKey(d)) {
                    if (window[d] == need[d])
                        valid--;
                    window[d]--;
                }
            }
        }
        
        return len == int.MaxValue ? "" : s.Substring(start, len);
    }
}

var minWindow = function(s, t) {
    if (s.length < t.length) return "";
    
    const tCount = {};
    for (let char of t) {
        tCount[char] = (tCount[char] || 0) + 1;
    }
    
    let left = 0;
    let right = 0;
    let minLen = Infinity;
    let minStart = 0;
    let required = Object.keys(tCount).length;
    let formed = 0;
    const windowCounts = {};
    
    while (right < s.length) {
        let char = s[right];
        windowCounts[char] = (windowCounts[char] || 0) + 1;
        
        if (tCount[char] && windowCounts[char] === tCount[char]) {
            formed++;
        }
        
        while (left <= right && formed === required) {
            if (right - left + 1 < minLen) {
                minLen = right - left + 1;
                minStart = left;
            }
            
            let leftChar = s[left];
            windowCounts[leftChar]--;
            if (tCount[leftChar] && windowCounts[leftChar] < tCount[leftChar]) {
                formed--;
            }
            left++;
        }
        
        right++;
    }
    
    return minLen === Infinity ? "" : s.substring(minStart, minStart + minLen);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

项目复杂度
时间复杂度O(m + n)
空间复杂度O(k)

其中 m 是字符串 s 的长度，n 是字符串 t 的长度，k 是字符集的大小（最多为 128 个 ASCII 字符）。每个字符最多被左右指针各访问一次，所以时间复杂度是线性的。

相关题目