-
Notifications
You must be signed in to change notification settings - Fork 3
/
substring.py
72 lines (67 loc) · 1.97 KB
/
substring.py
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
"""
Sliding Window Template:
start, end, uniqueCount = 0, 0, 0
freqDict = dict()
res = SOME_VAL
while end < len(s):
// increase the count of s[end] in freqDict
// maintain uniqeCount of chars
while uniqueCount condition:
update res to mind min
increase s[start] to make valid/invalid
modify uniqueCount
update d to find maximum
"""
# find max
def longest_substring_with_k_unique(s, k):
start, end, counter = 0, 0, 0
freqDict = dict()
res = 0
val = set()
while end < len(s):
freqDict[s[end]] = freqDict.get(s[end], 0) + 1
if freqDict[s[end]] == 1:
counter += 1
while counter > k:
freqDict[s[start]] -= 1
if freqDict[s[start]] < 1:
counter -= 1
start += 1
if res <= end - start + 1:
if res < end - start + 1:
val = set()
res = end - start + 1
val.add(s[start:end + 1])
end += 1
return res, val
def min_window_substring(s, t):
start, end, uniqueChars = 0, 0, 0
freqDict = dict()
minWinSS = ""
minWinRes = 10000000
# convert string t to freqDict
for c in t:
freqDict[c] = freqDict.get(c, 0) + 1
if freqDict[c] == 1:
uniqueChars += 1
while end < len(s):
if s[end] in freqDict:
freqDict[s[end]] -= 1
if freqDict[s[end]] == 0:
uniqueChars -= 1
while uniqueChars == 0:
if minWinRes > end-start+1:
minWinRes = end-start+1
minWinSS = s[start:end+1]
if s[start] in freqDict:
freqDict[s[start]] += 1
if freqDict[s[start]] > 0:
uniqueChars += 1
start += 1
end += 1
return minWinSS
if __name__ == "__main__":
s = "aabacbebebe"
k = 3
print(longest_substring_with_k_unique(s, k))
print(min_window_substring("this is a test string", "tist"))