## DEV Community π©βπ»π¨βπ» is a community of 970,177 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

ZeeshanAli-0704

Posted on

# Minimum Window Substring

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;
};