This is a new series where I document my struggles of leetcode questions hoping seeing however small of an audience I get gives me the motivation to continue.
This is a hard level question, but I feel like it probably belongs to medium-hard, rather than a full hard level.
The question is given two strings, you have to find the minimum window of string s which contains string t. Therefore:
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
we know from the example output that
1.) letters in t doesn't have to be in order
2.) the min window may contain many non-t characters
The example doesn't show, but we can have repeating characters in t as well. S can also have more of one t characters, like BBBBBADOBEC, than t has of that character, B.
The question itself gives away what you should do, use the sliding window technique to find the min window. The question is then really about, how do slide and make sure you'd have the min window for sure.
So the first thing we should do is to have a map of t characters, with the character as key and the number of each character as value. At each iteration when we push a character into the window, we check whether this character is in tMap. If it does, then we decrement the tMap[character]--. Therefore, when all counts of the characters in tMap are 0, it means we are in a possible min window. Think about this before we move on.
However, if you are a good leetcoder, you'd immediately know this is terrible performance and cannot possibly be the answer to a HARD level question.
So instead we will have a valid character tracker. This is to determine whether the current window has just the exact number of each character type in the tMap. So when this value is 0, we know we are currently in a valid window and should check whether it is a min window.
So this effectively prevents the looping on tMap. However, we have to be careful when we decrement this number. As you can see in s="BBBBBADOBEC", this string has too many Bs, if you just decrement the tracker when there is a matching character, then your tracker value can go beyond 0, which will be misleading.
Below is my code:
var minWindow = function(s, t) {
if(t.length > s.length) return '';
const tMap = t.split("").reduce(function(map, key){
map[key] ? map[key]++ : map[key] = 1;
return map;
},{});
tMap.value = t.length;
const window = [];
let min = s;
let hasAny = false; //because min = s
s.split("").forEach(function(letter){
window.push(letter);
if(letter in tMap) {
tMap[letter]--;
if(tMap[letter] >= 0) tMap.value--;
};
if(tMap.value === 0 ) {
hasAny=true;
while (window.length && !(window[0] in tMap)) {
//remove non-contributing characters
let current = window.shift();
}
min = Math.min(min.length, window.length) === min.length ?
min :
window.join('');
while (tMap.value === 0 ) {
//remove characters until room open
let current = window.shift();
if (current in tMap) {
tMap[current]++;
if(tMap[current] > 0) tMap.value++;
}
if(tMap.value === 0) {
min = Math.min(min.length, window.length) === min.length ?
min :
window.join('');
}
}
}
})
return hasAny ? min : "";
};
Woah this is big. Needless to say I did not have a good time debugging this. Allow me to walk you through.
1.) all codes before the .forEach should be reasonable, it's just setting up tMap. The hasAny is necessary for cases when nothing in s matches t, but the code may still return something instead of empty string because I set min to s. This may not be necessary in your setup.
2.) At each forEach iteration, the first thing we do is to push the string to the window, then decrement the tMap[letter] if possible, and additionally decrement tMap.value, the valid count number tracker I mentioned previously, if tMap[letter] >=0.
The ">= 0" part is crucial, this is where the magic lies that prevents you from falsely signal a valid min window, such as s="BBBBBB" and t="ABC".
3.) When tMap.value is 0, we have a valid min window, so we should check the window against current min.
4.) before checking against min, we should remove any leading non-contributing characters, such as in a possible window of "ZZZZZZZABC" for t = "ABC", we remove all the Zs before checking "ABC" against our min variable.
5.) When we are done, we should pop out one valid character out of the window so that tMap.value = 1.
This part is freaking tricky. The first use case to take for is the "BBBBBAC" for t="ABC". If you just shift out the very first B on the left, then tMap.value should not be 1, because there are still 1 of each character in t. So you can only increment the tracker when tMap[letter] > 0.
Secondly as you can see from the example, you might actually get a min window in the process of removing Bs. So we need to check if it's a min window when this while loop still valid.
Lastly, the end product of this while loop should be "AC", so that we can push a "B" into the window from the rest of the s string.
Wow, that was a lot, we are finally done with the question. WRONG!!!!!!!!
I didn't pass the submission because I exceeded the time limit. I don't really know what is wrong, I think it's probably something to do with the window being an array so pushing and joining probably took up a lot of time. Below is the passing solution from discussion:
var minWindowSlidingWindow = function (s, t) {
let min = "", left = 0, right = -1;
let map = {};
t.split('').forEach(element => {
if (map[element]==null) map[element] = 1;
else map[element] = map[element] + 1;
});
let count = Object.keys(map).length;
while (right <= s.length) {
if (count == 0) {
let current = s[left];
if (map[current] != null) map[current]++;
if (map[current] > 0) count++;
let temp = s.substring(left, right+1)
if (min == "") min = temp;
else min = min.length<temp.length?min:temp;
left++;
} else {
right++;
let current = s[right];
if (map[current] != null) map[current]--;
if (map[current] == 0) count--;
}
}
return min;
}
If you could understand my solution, then you should be able to understand this solution as well. THIS IS THE EXACT SAME ALGORITHM AFTER ALL .... fuck me...
The one thing that he had better than me is avoiding the while loops when count==0. The guy is smart, I definitely cannot do this at all, even if I can I'd probably be pretty bad at explaining why I don't have to during interview.
Since I thought that the only real difference between his and my answer is whether to use array or pointers to loop through the string, I modified my own code to use pointers instead out of spite and got it passing!
var minWindow = function(s, t) {
if(t.length > s.length) return '';
const tMap = t.split("").reduce(function(map, key){
map[key] ? map[key]++ : map[key] = 1;
return map;
},{});
tMap.absValue = t.length;
tMap.value = t.length;
let left = 0;
let right= -1;
let min = s;
let hasAny = false;
let subStr = '';
while(right < s.length) {
if (tMap.value != 0) {
right++
const letter = s[right];
if(letter in tMap) {
tMap[letter]--;
if(tMap[letter] >= 0) tMap.value--;
};
}
else {
hasAny=true;
while (!(s[left] in tMap)) {
//remove non-contributing characters
left++;
}
min = Math.min(min.length, right-left) === min.length ?
min :
s.substring(left, right+1);
while (tMap.value === 0 ) {
//remove characters until room open
if(tMap.value === 0) {
min = Math.min(min.length, right-left) === min.length ?
min :
s.substring(left, right+1);
}
let letter = s[left];
if (letter in tMap) {
tMap[letter]++;
if(tMap[letter] > 0) tMap.value++;
}
left++;
}
}
}
return hasAny ? min : "";
};
I like my solution, at least it's a code that documents the solution steps well so will probably be better received during interview. His is definitely a lot more impressive.
The takeaway for this question? Use pointers for sliding window. FUCK ME ... I wasted like 2 additional hours ish comparing and modifying my code.
Let me know anything on your mind after reading through this, THANKS!
Top comments (0)