Minimum Window Substring
Given two strings s and t of lengths m and n respectively, return the minimum window
substringof 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.
/**
* @param {string} s
* @param {string} t
* @return {string}
*/
var minWindow = function(s, t) {
if (t.length > s.length) return '';
const neededChars = {};
for (let char of t) {
neededChars[char] = (neededChars[char] || 0) + 1;
}
let left = 0;
let right = 0;
let neededLength = Object.keys(neededChars).length;
let substring = '';
while (right < s.length) {
const rightChar = s[right];
neededChars[rightChar]--;
if (neededChars[rightChar] === 0) neededLength--;
while (neededLength === 0) {
if (!substring || substring.length > right - left + 1) {
substring = s.slice(left, right + 1);
}
const leftChar = s[left];
// If the leftChar in charMap is at exactly 0 before being
// incremented, we now need more leftChars so that its count
// in charMap goes down to exactly 0
if (neededChars[leftChar] === 0) {
neededLength++;
}
neededChars[leftChar]++;
left++;
}
right++;
}
return substring;
};
Sliding window problems all follow a similar pattern
Posted by Jamie Meyer 18 days ago