nathanwailes

LeetCode 76 - Minimum Window Substring - NeetCode solution

Oct 16th, 2023
811
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.95 KB | None | 0 0
  1. class Solution:
  2.     def minWindow(self, s: str, t: str) -> str:
  3.         if t == "": return ""
  4.  
  5.         countT, window = {}, {}
  6.         for c in t:
  7.             countT[c] = 1 + countT.get(c, 0)
  8.  
  9.         have, need = 0, len(countT)
  10.         res, resLen = [-1, -1], float("infinity")
  11.         l = 0
  12.         for r in range(len(s)):
  13.             c = s[r]
  14.             window[c] = 1 + window.get(c, 0)
  15.  
  16.             if c in countT and window[c] == countT[c]:
  17.                 have += 1
  18.  
  19.             while have == need:
  20.                 # update our result
  21.                 if (r - l + 1) < resLen:
  22.                     res = [l, r]
  23.                     resLen = (r - l + 1)
  24.                 # pop from the left of our window
  25.                 window[s[l]] -= 1
  26.                 if s[l] in countT and window[s[l]] < countT[s[l]]:
  27.                     have -= 1
  28.                 l += 1
  29.         l, r = res
  30.         return s[l:r+1] if resLen != float("infinity") else ""
  31.  
Advertisement
Add Comment
Please, Sign In to add comment