daily pastebin goal
85%
SHARE
TWEET

Untitled

a guest Nov 19th, 2017 43 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import sys
  2.  
  3.  
  4. def find_min(characters):
  5.     min_i = sys.maxsize
  6.     for ch, i in characters.items():
  7.         if i < min_i:
  8.             min_i = i
  9.     return min_i
  10.  
  11.  
  12. def find_max(characters):
  13.     max_i = -1
  14.     for ch, i in characters.items():
  15.         if i > max_i:
  16.             max_i = i
  17.     return max_i
  18.  
  19.  
  20. def min_substring(S, T):
  21.     characters = {}
  22.     for ch in T:
  23.         if ch not in characters:
  24.             characters[ch] = -1
  25.  
  26.     min_i = -1
  27.     max_i = len(S)
  28.     min_length = len(S) + 1
  29.     matched = 0
  30.  
  31.     for i, ch in enumerate(S):
  32.         if ch not in characters:
  33.             continue
  34.  
  35.         if characters[ch] == -1:
  36.             matched += 1
  37.  
  38.         characters[ch] = i
  39.  
  40.         if matched < len(characters):
  41.             continue
  42.  
  43.         left_i = find_min(characters)
  44.         right_i = find_max(characters)
  45.         length = right_i - left_i
  46.         if length < min_length:
  47.             min_i = left_i
  48.             max_i = right_i
  49.             min_length = length
  50.  
  51.     return S[min_i:max_i + 1]
  52.  
  53.  
  54. if __name__ == '__main__':
  55.     print(min_substring('ADOBECODEBANC', 'ABC'))
RAW Paste Data
Top