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