class Solution:
def checkInclusion(self, t: str, s: str) -> bool:
need = {}
window = {}
for c in t:
need[c] = need.get(c, 0)+1
left = 0 # 窗口左边界
right = 0 # 窗口右边界
start = 0 # 记录子串起点
valid = 0 # t串与s串匹配次数
while right < len(s):
# 增大窗口
c = s[right]
right += 1
if c in need: # 该字符在t串中
window[c] = window.get(c, 0)+1
if window[c] == need[c]: # 该字符匹配
valid += 1
while right-left >= len(t):
if valid == len(need):
return True
d = s[left]
left += 1
if d in need:
if window[d] == need[d]:
valid -= 1
window[d] -= 1
return False
