LeetCode Meditations: Minimum Window Substring
Let's start with the description for Minimum Window String:
Given two strings
sandtof lengthsmandnrespectively, return the minimum window substring ofssuch that every character int(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.
For example:
minWindow('ADOBECODEBANC', 'ABC');
// -> 'BANC'
// The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.
minWindow('a', 'a');
// -> 'a'
// The entire string s is the minimum window.
minWindow('a', 'aa');
// -> ''
// Both 'a's from t must be included in the window.
// Since the largest window of s only has one 'a', return empty string.
minWindow('ADOBECODEBANC', 'ABC');
// -> 'BANC'
// The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.
minWindow('a', 'a');
// -> 'a'
// The entire string s is the minimum window.
minWindow('a', 'aa');
// -> ''
// Both 'a's from t must be included in the window.
// Since the largest window of s only has one 'a', return empty string.
This is the first problem in this series that is labeled as having the difficulty level of hard, and rightly so.
Let's look at one solution in TypeScript:
function minWindow(s: string, t: string): string {
if (t === '') {
return '';
}
let countT = new Map();
let window = new Map();
for (let i = 0; i < t.length; i++) {
if (countT.has(t[i])) {
countT.set(t[i], countT.get(t[i]) + 1);
} else {
countT.set(t[i], 0);
}
}
let have = 0;
let need = countT.size;
let result = '';
let resultLength = Infinity;
let left = 0;
let right = 0;
while (right < s.length) {
let char = s[right];
if (window.has(char)) {
window.set(char, window.get(char) + 1);
} else {
window.set(char, 0);
}
if (countT.has(char) && window.get(char) === countT.get(char)) {
have++;
}
while (have === need) {
if ((right - left + 1) < resultLength) {
result = s.slice(left, right + 1);
resultLength = right - left + 1;
}
window.set(s[left], window.get(s[left]) - 1);
if (countT.has(s[left]) && window.get(s[left]) < countT.get(s[left])) {
have--;
}
left++;
}
right++;
}
if (resultLength !== Infinity) {
return result;
} else {
return '';
}
};
function minWindow(s: string, t: string): string {
if (t === '') {
return '';
}
let countT = new Map();
let window = new Map();
for (let i = 0; i < t.length; i++) {
if (countT.has(t[i])) {
countT.set(t[i], countT.get(t[i]) + 1);
} else {
countT.set(t[i], 0);
}
}
let have = 0;
let need = countT.size;
let result = '';
let resultLength = Infinity;
let left = 0;
let right = 0;
while (right < s.length) {
let char = s[right];
if (window.has(char)) {
window.set(char, window.get(char) + 1);
} else {
window.set(char, 0);
}
if (countT.has(char) && window.get(char) === countT.get(char)) {
have++;
}
while (have === need) {
if ((right - left + 1) < resultLength) {
result = s.slice(left, right + 1);
resultLength = right - left + 1;
}
window.set(s[left], window.get(s[left]) - 1);
if (countT.has(s[left]) && window.get(s[left]) < countT.get(s[left])) {
have--;
}
left++;
}
right++;
}
if (resultLength !== Infinity) {
return result;
} else {
return '';
}
};
This solution is adapted from NeetCode.
First, we need to handle the case where t is empty; if so, we'll return an empty string.
We start by initializing two hash maps to hold characters for t and our current window. For example, if t is 'ABC', then countT will be this:
Map(3) { 'A' => 0, 'B' => 0, 'C' => 0 }
Map(3) { 'A' => 0, 'B' => 0, 'C' => 0 }
We'll have a variable named have to keep track of how many of the letters in t we have in our current window.
We also initialize a need variable with the size of countT to keep track of how many letters we need to have.
Then, we'll have result and resultLength that will be keeping track of the minimum window substring we've seen so far.
Then, starting with both left and right pointers pointing to the first index, we'll add each character to our window hash map. If the number of times the current character occurs in t is the same as the number of times it occurs in our current window, we'll increment our have variable.
That's good so far. Now let's look at this part:
while (have === need) {
if ((right - left + 1) < resultLength) {
result = s.slice(left, right + 1);
resultLength = right - left + 1;
}
window.set(s[left], window.get(s[left]) - 1);
if (countT.has(s[left]) && window.get(s[left]) < countT.get(s[left])) {
have--;
}
left++;
}
while (have === need) {
if ((right - left + 1) < resultLength) {
result = s.slice(left, right + 1);
resultLength = right - left + 1;
}
window.set(s[left], window.get(s[left]) - 1);
if (countT.has(s[left]) && window.get(s[left]) < countT.get(s[left])) {
have--;
}
left++;
}
Once what we have is equal to what we need, we'll do these things while they are still equal:
We'll first update our minimum result values (result and resultLength) if the length of our current window is less than their previous values.
Then, we'll see if we can do better. We'll first decrement the value of the left character in window. If it reaches below the value in countT, then we decrement our have variable because we lack that character in our current window at this point.
Note that, here, we'll only decrement the have variable when a character occurs less than the number of times it occurs in t. We can have more, we'll be fine with that. For example, if t is 'ABC', we'll be fine with having more than one 'A's in our current window.
Then, at this point, we'll also need to increment our left pointer so that we shrink our window and see if we can do better when it comes to the minimum value.
Once we have what we need, we'll return our result string, which is s sliced from the left index up to (and including) the right index.
However, if we don't have a result, we'll just return an empty string. And, that's all there is to it.
Time and space complexity
The time complexity of this solution is , as we have two main loops, one iterating over the elements of t, the other over the elements of s; each one has time complexity, making the overall time complexity .
The space complexity is , because the hash maps will be the dominant additional space, and they are constant, each having 26 items in total.
With the hardest (so far!), and the last problem of the Sliding Window chapter behind, we can finally start a new chapter on stacks. Until then, happy coding.