Advertisement
YeetMaster69

Minimum window substring

May 13th, 2022
756
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution:
  2.     def minWindow(self, s: str, t: str) -> str:
  3.         from collections import defaultdict
  4.         schars = defaultdict(int)
  5.         tchars = defaultdict(int)
  6.        
  7.         if len(t) > len(s):
  8.             return ""
  9.        
  10.         for i in t:
  11.             tchars[i] += 1
  12.        
  13.         currentMatch, requiredMatch = 0, len(tchars)
  14.        
  15.         left = 0
  16.        
  17.         currentAns = [-1, -1]
  18.         currentAnsLen = float('inf')
  19.        
  20.         for right in range(len(s)):    
  21.             if s[right] in tchars:              
  22.                 schars[s[right]] += 1
  23.                 if schars[s[right]] == tchars[s[right]]:
  24.                     currentMatch += 1
  25.             while currentMatch == requiredMatch:
  26.                 newAnsLen = right - left + 1
  27.                 if newAnsLen < currentAnsLen:
  28.                     currentAns = [left, right]
  29.                     currentAnsLen = newAnsLen
  30.  
  31.                 if s[left] in tchars:
  32.                     schars[s[left]] -= 1
  33.                     if schars[s[left]] == tchars[s[left]]-1:
  34.                         currentMatch -= 1
  35.                 left += 1
  36.                
  37.  
  38.         if currentAnsLen != float('inf'):
  39.             return s[currentAns[0]: currentAns[1]+1]
  40.         return ""
  41.            
  42.        
  43.        
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement