题解 | 最小覆盖子串

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param S string字符串 
# @param T string字符串 
# @return string字符串
#
class Solution:
    def minWindow(self , S: str, T: str) -> str:
        # write code here
        if not S or not T:
            return ""
        
        count_t = {}
        for char in T:
            count_t[char] = count_t.get(char,0)+1

        count_s = {}
        l,r = 0,0
        min_length = float("inf")
        min_start = 0
        formed = 0

        while r < len(S):
            char = S[r]
            count_s[char] = count_s.get(char,0)+1
            if char in count_t and count_t[char] == count_s[char]:
                formed += 1

            while l <= r and formed == len(count_t):
                char = S[l]
                if r -l +1 < min_length:
                    min_length = r-l+1
                    min_start = l
                count_s[char] -= 1
                if char in count_t and count_s[char] < count_t[char]:
                    formed -=1
                l += 1
                
            r += 1
        if min_length == float("inf"):
            return ""
        else:
            return S[min_start:min_start+min_length]