Minimum Window Substring

2 min read
String
LC-Hard
Sliding Window

Oct 21, 2022

3 years ago

LeetCode

Solution

Create char count map of t.
Iterate through s, while keeping track of char count
If matching char count, increment have
If counters for each character in t and s are same, we found a sliding window with all characters.
Update answer, while reducing the sliding window from the left, until our have doesn't match the needed
Remember to ignore characters that are not in t

Time	Space	Explanation
`O(n)`	`O(1)`	The charset is limited to 26 characters- and there's only one entry per character in the string for both the counters, so the space complexity is constant

def minWindow(self, s: str, t: str) -> str: if len(t) > len(s): return '' s_count = defaultdict(lambda: 0) t_count = Counter(t) l = have = 0 needed = len(t_count.keys()) ans = None for r in range(len(s)): ch = s[r] s_count[ch] += 1 if ch in t_count and s_count[ch] == t_count[ch]: have += 1 while have == needed: if ans is None or r - l + 1 < (ans[1] - ans[0] + 1): ans = [l, r] ch = s[l] s_count[ch] -= 1 if ch in t_count and s_count[ch] + 1 == t_count[ch]: have -= 1 l += 1 if ans is None: return '' return s[ans[0]:ans[1]+1]