python-leetcode-最小覆盖子串

76. 最小覆盖子串 - 力扣（LeetCode）

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not s or not t:
            return ""
        
        need = {}
        for c in t:
            need[c] = need.get(c, 0) + 1
        window = {}
        left = right = 0
        valid = 0  # 满足条件的字符数
        start = 0  # 最小子串的起始索引
        min_len = 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 += 1
            
            # 尝试收缩窗口
            while valid == len(need):
                # 更新最小子串
                if right - left < min_len:
                    start = left
                    min_len = right - left
                    
                d = s[left]
                left += 1
                if d in need:
                    if window[d] == need[d]:
                        valid -= 1
                    window[d] -= 1
        
        return s[start:start + min_len] if min_len != float('inf') else ""