Advertisement
hoangreal

Find shortest substring that contains all the letters in the dictionary

Oct 21st, 2024
68
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.82 KB | Source Code | 0 0
  1. """
  2. given a string and dictionary find the shortest substring containing all chars in dictionary
  3. """
  4.  
  5. from collections import defaultdict
  6.  
  7. def find_min_window(S: str, T: list[str]):
  8.     left, right = 0, 0
  9.     c = defaultdict(int) # frequency count for T
  10.    
  11.     for ch in T:
  12.         c[ch] += 1
  13.    
  14.     min_str = None
  15.    
  16.     while right <= len(S):
  17.         if all(x <= 0 for x in c.values()):
  18.             if min_str is None or right - left <= len(min_str):
  19.                 min_str = S[left:right]
  20.            
  21.             if S[left] in c:
  22.                 c[S[left]] += 1
  23.             left += 1
  24.         else:
  25.             if right == len(S):
  26.                 break
  27.            
  28.             if S[right] in c:
  29.                 c[S[right]] -= 1
  30.             right += 1
  31.    
  32.     return min_str if min_str else ''
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement