76. Minimum Window Substring
Don’t know why it’s labelled as a hard, but good sliding window problem.
Improvable items (thanks chatgpt):
- Avoid O(Σ) checks each step. satisfactory() scans 52 slots every time the window changes. Keep a running count of how many required characters are currently satisfied will make each step O(1).
- Use direct ASCII buckets or Counter. Arrays of size 128 (or 256) avoid the custom idx and handle both cases naturally. It’s also clearer than ord>=97 tricks. (Or use collections.Counter.)
1class Solution:
2 def minWindow(self, s: str, t: str) -> str:
3 # print(ord("A")) # 65
4 # print(ord("a")) # 97
5
6 # [A, B, ...., Y, Z, a, b, ..., y, z]
7 s_store = [0] * 26 * 2
8 t_store = [0] * 26 * 2
9
10 def idx(c):
11 o = ord(c)
12 if o >= 97:
13 return o - 97 + 26
14 return o - 65
15
16 # print(idx("a")) # 26
17 # print(idx("b")) # 27
18 # print(idx("A")) # 0
19 # print(idx("B")) # 1
20
21 # t str into t_store
22 for c in t:
23 t_store[idx(c)] += 1
24
25 def satisfactory() -> bool:
26 for i in range(52):
27 if t_store[i] > s_store[i]:
28 return False
29 return True
30
31 # let's go sliding
32 l = 0
33 min_window = [10**6, -1, -1] # [length, l, r (both inclusive)]
34
35 for r, c in enumerate(s):
36 # expand r till satisfactory
37 # shrink l till non satis
38 s_store[idx(c)] += 1
39
40 while satisfactory() and l <= r:
41 if r - l + 1 < min_window[0]:
42 min_window = [r - l + 1, l, r]
43
44 s_store[idx(s[l])] -= 1
45 l += 1
46
47 return s[min_window[1] : min_window[2] + 1] if min_window[1] > -1 else ""
#Neetcode150 #Sliding-Window #Python #Revisit