题解 | #最小覆盖子串#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param S string字符串 
# @param T string字符串 
# @return string字符串
from itertools import combinations
import traceback
class Solution:
    def minWindow(self , S: str, T: str) -> str:
        # write code here
        try:
            if len(S) < len(T):
                return ''
            if len(S) == len(T):
                if S == T:
                    return S
                else:
                    return ''
            l = 0
            r = 0
            res = ''
            best_count = float('inf')
            T_map = {}
            for _ in T:
                if _ in T_map:
                    T_map[_] += 1
                else:
                    T_map[_] = 1
            
            match_map = {}
            lenght_T_map = len(T_map) # 需要匹配的单词数，包含重复的：如AA，计数1
            n = 0 # 表示已经匹配的单词数


            while r < len(S):
                # w = S[l:r+1]
                # 核心难点T中存在多个重复字母，如：AA，需要在窗口中匹配多次AA，才能做匹配计数+1
                r_s = S[r]
                if r_s in T:
                    if r_s in match_map:
                        match_map[r_s] += 1
                    else:
                        match_map[r_s] = 1
                    if match_map[r_s] == T_map[r_s]:
                        n += 1

                while  n == lenght_T_map:
                    l_s = S[l]
                    w = S[l:r+1]
                    if len(w) <= best_count:
                        res = w
                        best_count = len(w)
                    if l_s in T:
                        match_map[l_s] -= 1
                        if match_map[l_s] < T_map[l_s]:
                            n -= 1
                    l += 1


                r += 1
            return res


        except:
            print(traceback.format_exc())