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.
A substring is a contiguous sequence of characters within the string.
Example 1:
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.
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--;
right++;
while (neededLength === 0) {
if (!substring || substring.length > right - left) {
substring = s.slice(left, right);
}
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++;
}
}
return substring;
};
console.log(minWindow("ADOBECODEBANC", "ABC"));
console.log(minWindow("ab", "a"));
Top comments (0)