Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- """
- given a string and dictionary find the shortest substring containing all chars in dictionary
- """
- from collections import defaultdict
- def find_min_window(S: str, T: list[str]):
- left, right = 0, 0
- c = defaultdict(int) # frequency count for T
- for ch in T:
- c[ch] += 1
- min_str = None
- while right <= len(S):
- if all(x <= 0 for x in c.values()):
- if min_str is None or right - left <= len(min_str):
- min_str = S[left:right]
- if S[left] in c:
- c[S[left]] += 1
- left += 1
- else:
- if right == len(S):
- break
- if S[right] in c:
- c[S[right]] -= 1
- right += 1
- return min_str if min_str else ''
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement