Given strings s and t, return the shortest substring of s that contains every character of t, counting repeats (if t has two as, the substring needs at least two as). If no such substring exists, return the empty string "". The answer is unique for the given tests.
"BANC" holds one A, one B and one C, and no shorter window does.t needs two as but s has only one.- 1 <= s.length, t.length <= 10^5
- Both strings contain uppercase and lowercase English letters
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Checking every substring is O(n^2) windows, each needing a check. Use a sliding window instead. Move the right end forward until the window covers t. Then the window is valid, and moving the left end forward can only make it shorter, so shrink it as far as possible while it stays valid, recording the best length. When it stops being valid, grow the right end again. A counter of "characters still missing" tells us in O(1) whether the window is valid.
Algorithm
- Count the letters of
tinneed, and setmissing = len(t). - For each
right: ifneed[s[right]] > 0, decreasemissing; then decreaseneed[s[right]]. - While
missing == 0: record the window if it is the shortest so far, then increaseneed[s[left]]; if it becomes positive, increasemissing. Moveleftright. - Return the best window, or
""if none was found.
O(|s| + |t|)Space: O(1) for a fixed alphabet (128 counters)need go negative is the trick: negative values mean the window has extra copies, so removing them does not break validity. Be careful that case matters: a and A are different characters.class Solution: def minWindow(self, s: str, t: str) -> str: need = Counter(t) missing = len(t) left = 0 best_start, best_len = 0, float('inf') for right, c in enumerate(s): if need[c] > 0: missing -= 1 # this copy was still needed need[c] -= 1 while missing == 0: # window covers t: try to shrink it if right - left + 1 < best_len: best_start, best_len = left, right - left + 1 d = s[left] need[d] += 1 if need[d] > 0: missing += 1 # removed a needed copy left += 1 return "" if best_len == float('inf') else s[best_start:best_start + best_len]