python-programs/substring.py at master · kumaya/python-programs · GitHub

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
deflongest_substring_with_k_unique(s, k):
start, end, counter=0, 0, 0
freqDict=dict()
res=0
val=set()
whileend<len(s):
freqDict[s[end]] =freqDict.get(s[end], 0) +1
iffreqDict[s[end]] ==1:
counter+=1
whilecounter>k:
freqDict[s[start]] -=1
iffreqDict[s[start]] <1:
counter-=1
start+=1
ifres<=end-start+1:
ifres<end-start+1:
val=set()
res=end-start+1
val.add(s[start:end+1])
end+=1
returnres, val

defmin_window_substring(s, t):
start, end, uniqueChars=0, 0, 0
freqDict=dict()
minWinSS=""
minWinRes=10000000
# convert string t to freqDict
forcint:
freqDict[c] =freqDict.get(c, 0) +1
iffreqDict[c] ==1:
uniqueChars+=1

whileend<len(s):
ifs[end] infreqDict:
freqDict[s[end]] -=1
iffreqDict[s[end]] ==0:
uniqueChars-=1
whileuniqueChars==0:
ifminWinRes>end-start+1:
minWinRes=end-start+1
minWinSS=s[start:end+1]
ifs[start] infreqDict:
freqDict[s[start]] +=1
iffreqDict[s[start]] >0:
uniqueChars+=1
start+=1
end+=1
returnminWinSS


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"))