Minimum Window Substring(LeetCode)
Problem Statement​
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.
Examples​
Example 1:
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.
Example 2:
Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.
Example 3:
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​
m == s.length
n == t.length
1 <= m, n <= 105
s
andt
consist of uppercase and lowercase English letters.
Solution​
Approach 1: C++​
Algorithm​
- Initialization:
- Create a
map
to count characters int
. - Initialize
counter
to the length oft
, begin and end pointers to 0,d
(length of the minimum window) toINT_MAX
, andhead
to 0.
- Expand the Window:
- Move the
end
pointer to expand the window. - Decrease the count in
map
for the current character ins
. - If the count in
map
is greater than 0, decrementcounter
.
- Shrink the Window:
- When
counter
is 0, try to shrink the window by moving thebegin
pointer. - If the new window size is smaller, update
head
andd
. - Increase the count in
map
for the character atbegin
. - If the count in
map
becomes positive, incrementcounter
.
- Return Result:
- If
d
is stillINT_MAX
, return an empty string. - Otherwise, return the substring starting from
head
with lengthd
.
Implementation​
class Solution {
public:
string minWindow(string s, string t) {
vector<int> map(128, 0);
for (char c : t) {
map[c]++;
}
int counter = t.size(), begin = 0, end = 0, d = INT_MAX, head = 0;
while (end < s.size()) {
if (map[s[end++]]-- > 0) {
counter--;
}
while (counter == 0) {
if (end - begin < d) {
head = begin;
d = end - head;
}
if (map[s[begin++]]++ == 0) {
counter++;
}
}
}
return d == INT_MAX ? "" : s.substr(head, d);
}
};
Complexity Analysis​
- Time complexity:
- Space complexity:
Approach 2: Python​
Algorithm​
- Initialization:
- Create a
needstr
dictionary to count characters int
. - Initialize
needcnt
to the length oft
,res
to store the result window, andstart
to 0.
- Expand the Window:
- Move the
end
pointer to expand the window. - Decrease the count in
needstr
for the current character ins
. - If the count in
needstr
is greater than 0, decrementneedcnt
.
- Shrink the Window:
- When
needcnt
is 0, try to shrink the window by moving thestart
pointer. - Adjust the count in
needstr
for the character atstart
. - If the count in
needstr
becomes positive, incrementneedcnt
.
- Return Result:
- If the result window is valid, return the substring.
- Otherwise, return an empty string.
Implementation​
class Solution:
def minWindow(self, s: str, t: str) -> str:
if len(s) < len(t):
return ""
needstr = collections.defaultdict(int)
for ch in t:
needstr[ch] += 1
needcnt = len(t)
res = (0, float('inf'))
start = 0
for end, ch in enumerate(s):
if needstr[ch] > 0:
needcnt -= 1
needstr[ch] -= 1
if needcnt == 0:
while True:
tmp = s[start]
if needstr[tmp] == 0:
break
needstr[tmp] += 1
start += 1
if end - start < res[1] - res[0]:
res = (start, end)
needstr[s[start]] += 1
needcnt += 1
start += 1
return '' if res[1] > len(s) else s[res[0]:res[1]+1]
Complexity Analysis​
- Time complexity:
- Space complexity:
Conclusion​
The C++ and Python approaches for finding the minimum window substring are quite similar in their methodology. Both utilize the two-pointer technique, also known as the sliding window approach, to efficiently traverse the string s and dynamically adjust the window to find the smallest valid substring containing all characters of the string t. They maintain a character count map to keep track of the required characters from t and adjust the counts as the window expands and contracts. Additionally, both solutions use a counter variable to monitor the number of characters still needed to form a valid window.