Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution:
- def minWindow(self, s: str, t: str) -> str:
- from collections import defaultdict
- schars = defaultdict(int)
- tchars = defaultdict(int)
- if len(t) > len(s):
- return ""
- for i in t:
- tchars[i] += 1
- currentMatch, requiredMatch = 0, len(tchars)
- left = 0
- currentAns = [-1, -1]
- currentAnsLen = float('inf')
- for right in range(len(s)):
- if s[right] in tchars:
- schars[s[right]] += 1
- if schars[s[right]] == tchars[s[right]]:
- currentMatch += 1
- while currentMatch == requiredMatch:
- newAnsLen = right - left + 1
- if newAnsLen < currentAnsLen:
- currentAns = [left, right]
- currentAnsLen = newAnsLen
- if s[left] in tchars:
- schars[s[left]] -= 1
- if schars[s[left]] == tchars[s[left]]-1:
- currentMatch -= 1
- left += 1
- if currentAnsLen != float('inf'):
- return s[currentAns[0]: currentAns[1]+1]
- return ""
Advertisement
Advertisement
Advertisement
RAW Paste Data
Copied
Advertisement