forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathyolophg.py
More file actions
40 lines (34 loc) · 1.62 KB
/
yolophg.py
File metadata and controls
40 lines (34 loc) · 1.62 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
# Time Complexity: O(N) - go through the string with two pointers, so it's basically O(N).
# Space Complexity: O(1) - only storing character frequencies (max 52 keys for a-z & A-Z), so it's effectively constant space.
class Solution:
def minWindow(self, s: str, t: str) -> str:
# store character counts for t
target_count = Counter(t)
# window character count
window_count = defaultdict(int)
# start of the window
left = 0
# min substring
min_substring = ""
# tracks how many characters match the required count
matched_chars = 0
# unique characters needed
required_chars = len(target_count)
for right, char in enumerate(s):
# expand window by adding the rightmost character
if char in target_count:
window_count[char] += 1
if window_count[char] == target_count[char]:
matched_chars += 1
# try shrinking the window if all required characters are present
while matched_chars == required_chars:
# update min substring if this one is shorter
if min_substring == "" or (right - left + 1) < len(min_substring):
min_substring = s[left:right + 1]
# remove leftmost character and move left pointer
if s[left] in window_count:
window_count[s[left]] -= 1
if window_count[s[left]] < target_count[s[left]]:
matched_chars -= 1
left += 1
return min_substring