-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMinimum Window Substring
More file actions
38 lines (30 loc) · 1.2 KB
/
Minimum Window Substring
File metadata and controls
38 lines (30 loc) · 1.2 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
from collections import Counter
class Solution:
def minWindow(self, s, t):
if len(t) > len(s):
return ""
minLength = len(s) + 1
count_t = Counter(t)
distincts = len(count_t) #Number of distinct characters in "t"
l,r = 0,0 #Pointers for the sliding window
# Keep the starting and ending index of the smallest window
minI = -1
minJ = -1
while r < len(s):
if s[r] in count_t:
count_t[s[r]] -= 1
if count_t[s[r]] == 0:
distincts -= 1
while distincts == 0:
if r - l + 1 < minLength:
minLength = r - l + 1
minI = l
minJ = r
if s[l] in count_t:
count_t[s[l]] += 1
if count_t[s[l]] == 1:
distincts += 1
l += 1
r += 1
substring = s[minI:minJ + 1]
return substring