76 Minimum Window Substring
76 Minimum Window Substring
Minimum Window Substring 
Given two strings s and t of lengths m and n 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.
Example 1:
1
2
3
4
5
**Input:** s = "ADOBECODEBANC", t = "ABC"
**Output:** "BANC"
**Explanation:** The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.
Example 2:
1
2
3
4
5
**Input:** s = "a", t = "a"
**Output:** "a"
**Explanation:** The entire string s is the minimum window.
Example 3:
1
2
3
4
5
6
**Input:** s = "a", t = "aa"
**Output:** ""
**Explanation:** Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.
Constraints:
1
2
3
4
m == s.length
n == t.length
1 <= m, n <= 105
s and t consist of uppercase and lowercase English letters.
Follow up: Could you find an algorithm that runs in O(m + n) time?
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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
class Solution:
def minWindow(self, s: str, t: str) -> str:
if not t or not s:
return ""
from collections import Counter
t_count = Counter(t)
current_count = Counter()
start = 0
min_len = float('inf')
min_start = 0
required = len(t_count)
formed = 0
l, r = 0, 0
while r < len(s):
character = s[r]
current_count[character] += 1
if character in t_count and current_count[character] == t_count[character]:
formed += 1
while l <= r and formed == required:
character = s[l]
if r - l + 1 < min_len:
min_len = r - l + 1
min_start = l
current_count[character] -= 1
if character in t_count and current_count[character] < t_count[character]:
formed -= 1
l += 1
r += 1
if min_len == float('inf'):
return ""
else:
return s[min_start:min_start + min_len]
def contains(self, k : str, ls : [int]) -> bool:
if k.isupper():
return ls[ord(k)-65] != 5000
else:
return ls[ord(k.upper())-39] != 5000
def reduce(self, k : str, ls : [int] ) -> [int]:
if k.isupper():
ls[ord(k)-65] = ls[ord(k)-65] - 1
else:
ls[ord(k.upper())-39] = ls[ord(k.upper())-39] - 1
return ls
def increase(self, k : str, ls : [int] ) -> [int]:
if k.isupper():
ls[ord(k)-65] = ls[ord(k)-65] + 1
else:
ls[ord(k.upper())-39] = ls[ord(k.upper())-39] + 1
return ls
def get(self, k : str, ls : [int]) -> int:
if k.isupper():
return ls[ord(k)-65]
else:
return ls[ord(k.upper())-39]
def is_complete(self, s : str, ls : [int]) -> bool:
for k in s:
if k.isupper():
if not ls[ord(k)-65] <= 0:
return False
else:
print(s, False)
if not ls[ord(k.upper())-39] <= 0:
return False
return True
This post is licensed under CC BY 4.0 by the author.