DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’»

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.

Create account Log in
ZeeshanAli-0704
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;
};
console.log(minWindow("ADOBECODEBANC", "ABC"));
console.log(minWindow("ab", "a"));


Enter fullscreen mode Exit fullscreen mode

Top comments (0)

Visualizing Promises and Async/Await 🀯

async await

☝️ Check out this all-time classic DEV post