blob: 9ea7da130b4e8c9e36952767f055a0abeed46616 (
plain)
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
|
# 76. Minimum Window Substring
from collections import defaultdict
"""
given two strings 's' and 't' of length 'n' and 'm' respectively, return the
minimum window substring of 's' such that every character in 't' (including
duplicates) is included in the window. if there is no such substring, return
the empty string. the testcases will be generated such that the answer is
unique.
"""
class Solution(object):
def minWindow(self, s, t):
"""
:type s: str
:type t: str
:rtype: str
"""
if not s or not t:
return ""
dict_t = defaultdict(int)
for c in t:
dict_t[c] += 1
required = len(dict_t)
l, r = 0, 0
formed = 0
windowCounts = defaultdict(int)
ans = [-1, 0, 0]
while r < len(s):
c = s[r]
windowCounts[c] += 1
if c in dict_t and windowCounts[c] == dict_t[c]:
formed += 1
while l <= r and formed == required:
c = s[l]
if ans[0] == -1 or r - l + 1 < ans[0]:
ans[0] = r - l + 1
ans[1] = l
ans[2] = r
windowCounts[c] -= 1
if c in dict_t and windowCounts[c] < dict_t[c]:
formed -= 1
l += 1
r += 1
return "" if ans[0] == -1 else s[ans[1] : ans[2] + 1]
if __name__ == "__main__":
obj = Solution()
print(obj.minWindow(s="ADOBECODEBANC", t="ABC"))
print(obj.minWindow(s="a", t="a"))
print(obj.minWindow(s="a", t="aa"))
|