| 1 | # minimum window substring leetcode hard 76 |
| 2 | class Solution: |
| 3 | def minWindow(self, s: str, t: str) -> str: |
| 4 | if t == "": return "" |
| 5 | countT, window = {}, {} |
| 6 | res, resLen = [-1,-1], float("inf") |
| 7 | l = 0 |
| 8 | for c in t: |
| 9 | countT[c] = 1 + countT.get(c, 0) |
| 10 | have, need = 0, len(countT) |
| 11 | |
| 12 | for r in range(len(s)): |
| 13 | c = s[r] |
| 14 | window[c] = 1 + window.get(c, 0) |
| 15 | if c in countT and window[c] == countT[c]: |
| 16 | have += 1 |
| 17 | while have == need: |
| 18 | # update our result |
| 19 | if (r - l + 1) < resLen: |
| 20 | res = [l, r] |
| 21 | resLen = (r - l + 1) |
| 22 | # pop from the left |
| 23 | window[s[l]] -= 1 |
| 24 | if s[l] in countT and window[s[l]] < countT[s[l]]: |
| 25 | have -= 1 |
| 26 | l += 1 |
| 27 | l, r = res |
| 28 | c = "a" |
| 29 | print(window) |
| 30 | return s[l:r + 1] if resLen != float("infinity") else "" |
| 31 | print(Solution().minWindow("ADOBECODEBANC", "ABC")) |