题解 | #最小覆盖子串#

https://www.nowcoder.com/practice/c466d480d20c4c7c9d322d12ca7955ac

```#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @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())
```

08-14 11:09