Minimum Window Substring in DSA Javascript - Build from Scratch

Minimum Window Substring

📖 Scenario: Imagine you are working on a text search feature for a document editor. You want to find the smallest part of the document that contains all the letters of a search query.

🎯 Goal: Build a program that finds the minimum window substring in a given string s that contains all characters of another string t.

📋 What You'll Learn

Create a string variable s with the value "ADOBECODEBANC".

Create a string variable t with the value "ABC".

Create a function minWindow that takes two strings s and t and returns the minimum window substring of s containing all characters of t.

Print the result of calling minWindow(s, t).

💡 Why This Matters

🌍 Real World

Text editors, search engines, and data filtering tools often need to find the smallest segment of text containing certain keywords or characters.

💼 Career

Understanding sliding window techniques and frequency counting is essential for software engineers working on string processing, search algorithms, and performance optimization.

1

Create the input strings

Create a string variable s with the value "ADOBECODEBANC" and a string variable t with the value "ABC".

DSA Javascript

// Create string variables s and t with given values
// Your code here

Hint

Use const to create variables s and t with the exact given string values.

2

Set up character frequency map for t

Create a function minWindow that takes parameters s and t. Inside it, create a Map called need to count the frequency of each character in t.

DSA Javascript

const s = "ADOBECODEBANC";
const t = "ABC";

function minWindow(s, t) {
    // Create a Map called need to count characters in t
    // Your code here
}

Hint

Use a for...of loop to count each character in t and store counts in need Map.

3

Implement sliding window to find minimum substring

Inside minWindow, create variables window as a Map, have and needCount as numbers, and res as an array to store start and end indices and length. Use two pointers left and right to slide over s. Expand right pointer to include characters and update window counts. When have equals needCount, try to shrink the window from left to find smaller valid windows. Return the substring of s that is the smallest window containing all characters of t.

DSA Javascript

const s = "ADOBECODEBANC";
const t = "ABC";

function minWindow(s, t) {
    const need = new Map();
    for (const char of t) {
        need.set(char, (need.get(char) || 0) + 1);
    }
    // Implement sliding window logic here
    // Your code here
}

Hint

Use two pointers left and right to expand and shrink the window. Update counts in window Map and track how many needed characters are matched with have.

4

Print the minimum window substring

Print the result of calling minWindow(s, t).

DSA Javascript

const s = "ADOBECODEBANC";
const t = "ABC";

function minWindow(s, t) {
    const need = new Map();
    for (const char of t) {
        need.set(char, (need.get(char) || 0) + 1);
    }
    const window = new Map();
    let have = 0;
    const needCount = need.size;
    let res = [-1, -1];
    let resLen = Infinity;
    let left = 0;

    for (let right = 0; right < s.length; right++) {
        const c = s[right];
        window.set(c, (window.get(c) || 0) + 1);

        if (need.has(c) && window.get(c) === need.get(c)) {
            have++;
        }

        while (have === needCount) {
            if ((right - left + 1) < resLen) {
                res = [left, right];
                resLen = right - left + 1;
            }
            const leftChar = s[left];
            window.set(leftChar, window.get(leftChar) - 1);
            if (need.has(leftChar) && window.get(leftChar) < need.get(leftChar)) {
                have--;
            }
            left++;
        }
    }

    return resLen === Infinity ? "" : s.slice(res[0], res[1] + 1);
}

// Print the minimum window substring
// Your code here

Hint

Use console.log(minWindow(s, t)) to print the smallest substring containing all characters of t.

Practice

1. What does the "Minimum Window Substring" problem ask you to find given two strings s and t?

easy

A. The number of times t appears in s

B. The longest substring in s that does not contain any character from t

C. The smallest substring in s that contains all characters of t

D. The substring of s that is exactly equal to t

Solution

1. Step 1: Understand the problem goal

   The problem asks to find the smallest part of string s that has all characters from string t, including duplicates.

2. Step 2: Compare options with the problem statement

   The smallest substring in s that contains all characters of t matches this goal exactly. Other options describe different problems.

3. Final Answer:

   The smallest substring in s that contains all characters of t -> Option C

4. Quick Check:

   Minimum Window Substring = smallest substring with all chars [OK]

Hint: Look for smallest substring covering all chars of target [OK]

Common Mistakes:

• Confusing longest substring with smallest
• Ignoring duplicate characters in t
• Thinking it counts occurrences instead of substring

2. Which of the following JavaScript code snippets correctly initializes a frequency map for characters in string t?

easy

A. const freq = {}; for (const char of t) { freq[char] = (freq[char] || 0) + 1; }

B. const freq = new Map(); for (const char of t) { freq.set(char, freq.get(char) + 1); }

C. const freq = {}; for (let i = 0; i < t.length; i++) { freq[t[i]] = freq[t[i]] + 1; }

D. const freq = []; for (const char of t) { freq[char] += 1; }

Solution

1. Step 1: Check initialization and increment logic

   const freq = {}; for (const char of t) { freq[char] = (freq[char] || 0) + 1; } initializes an empty object and increments counts safely using freq[char] = (freq[char] || 0) + 1, which works even if freq[char] is undefined.

2. Step 2: Identify errors in other options

   const freq = new Map(); for (const char of t) { freq.set(char, freq.get(char) + 1); } tries to use Map but calls freq.get(char) + 1 without checking if freq.get(char) is undefined, causing NaN. const freq = {}; for (let i = 0; i < t.length; i++) { freq[t[i]] = freq[t[i]] + 1; } tries to add 1 to undefined without default. const freq = []; for (const char of t) { freq[char] += 1; } uses an array but accesses with string keys, which is invalid.

3. Final Answer:

   const freq = {}; for (const char of t) { freq[char] = (freq[char] || 0) + 1; } -> Option A

4. Quick Check:

   Safe frequency map init = const freq = {}; for (const char of t) { freq[char] = (freq[char] || 0) + 1; } [OK]

Hint: Use (freq[char] || 0) + 1 to safely count chars [OK]

Common Mistakes:

• Not initializing counts before adding
• Using Map without checking undefined values
• Using array with string keys

3. What will be the output of the following JavaScript code snippet?

const s = "ADOBECODEBANC";
const t = "ABC";

function minWindow(s, t) {
  const need = {};
  for (const c of t) need[c] = (need[c] || 0) + 1;
  let left = 0, right = 0, count = t.length;
  let minLen = Infinity, start = 0;

  while (right < s.length) {
    if (need[s[right]] > 0) count--;
    need[s[right]] = (need[s[right]] || 0) - 1;
    right++;

    while (count === 0) {
      if (right - left < minLen) {
        minLen = right - left;
        start = left;
      }
      need[s[left]]++;
      if (need[s[left]] > 0) count++;
      left++;
    }
  }
  return minLen === Infinity ? "" : s.substring(start, start + minLen);
}

console.log(minWindow(s, t));

medium

A. "DOBECODEBA"

B. "ADOBEC"

C. "CODEBA"

D. "BANC"

Solution

1. Step 1: Understand the sliding window logic

   The code uses two pointers expanding and shrinking a window over s. It tracks needed characters from t and shrinks window when all are found.

2. Step 2: Trace the window to find minimum substring

   For s = "ADOBECODEBANC" and t = "ABC", the smallest substring containing all chars is "BANC" starting at index 9 with length 4.

3. Final Answer:

   "BANC" -> Option D

4. Quick Check:

   Minimum window substring = "BANC" [OK]

Hint: Trace sliding window to find smallest valid substring [OK]

Common Mistakes:

• Confusing substring start and end indices
• Not updating minimum length correctly
• Ignoring character counts when shrinking window

4. Identify the bug in this JavaScript function for Minimum Window Substring:

function minWindow(s, t) {
  const need = {};
  for (const c of t) need[c] = (need[c] || 0) + 1;
  let left = 0, right = 0, count = t.length;
  let minLen = Infinity, start = 0;

  while (right < s.length) {
    if (need[s[right]] > 0) count--;
    need[s[right]]--;
    right++;

    while (count === 0) {
      if (right - left < minLen) {
        minLen = right - left;
        start = left;
      }
      need[s[left]]++;
      if (need[s[left]] > 0) count++;
      left++;
    }
  }
  return minLen === Infinity ? "" : s.substring(start, start + minLen);
}

medium

A. The count variable should be initialized to 0 instead of t.length

B. The decrement of need[s[right]] should use (need[s[right]] || 0) - 1 to avoid undefined

C. The inner while loop condition should be count > 0 instead of count === 0

D. The substring returned should use s.substring(start, right) instead of s.substring(start, start + minLen)

Solution

1. Step 1: Check how need map is updated

   The code does need[s[right]]-- without ensuring need[s[right]] is defined. If s[right] is not in t, need[s[right]] is undefined, causing NaN on decrement.

2. Step 2: Fix by defaulting undefined to 0 before decrement

   Use need[s[right]] = (need[s[right]] || 0) - 1 to avoid NaN and keep counts correct.

3. Final Answer:

   The decrement of need[s[right]] should use (need[s[right]] || 0) - 1 to avoid undefined -> Option B

4. Quick Check:

   Safe decrement with default 0 avoids NaN [OK]

Hint: Always default undefined to 0 before decrementing counts [OK]

Common Mistakes:

• Not handling characters not in t
• Wrong initialization of count variable
• Incorrect substring slicing

5. Given strings s = "aabbccdd" and t = "abc", what is the minimum window substring that contains all characters of t considering duplicates in t only once?

hard

A. "abbc"

B. "abc"

C. "aabbc"

D. "bcca"

Solution

1. Step 1: Understand character requirements from t

   String t = "abc" has characters 'a', 'b', 'c' each once. So the window must contain at least one 'a', one 'b', and one 'c'.

2. Step 2: Find smallest substring in s containing 'a', 'b', 'c'

   In s = "aabbccdd", the substring "abc" starting at index 1 (characters at indices 1:'a', 2:'b', 3:'b', 4:'c') is not contiguous as "abc" is not directly present, but the smallest substring containing all characters once is actually "abc" starting at index 1 or 2. However, the substring "abc" is present starting at index 1 to 3 ("abb") is missing 'c', so the smallest substring containing all is "abc" at indices 1 to 3 is invalid. The substring "abbc" (indices 1 to 4) contains all characters and is minimal. But the substring "abc" (indices 1 to 3) is missing 'c'. The substring "abc" (indices 2 to 4) is "bbc" missing 'a'. The substring "abc" (indices 0 to 2) is "aab" missing 'c'. The substring "abc" (indices 3 to 5) is "bcc" missing 'a'. The substring "abc" (indices 1 to 4) is "abbc" which contains all. The substring "abc" (indices 1 to 3) is "abb" missing 'c'. The substring "abc" (indices 2 to 4) is "bbc" missing 'a'. The substring "abc" (indices 0 to 4) is "aabbc" which is longer. The substring "abc" (indices 1 to 4) "abbc" is the smallest substring containing all characters once. However, the option "abc" is present as "abc", but it is not a substring of s. So the correct minimal substring is "abbc".

3. Final Answer:

   "abbc" -> Option A

4. Quick Check:

   Minimum window with all chars once = "abbc" [OK]

Hint: Count chars in t once; find smallest substring covering them [OK]

Common Mistakes:

• Counting duplicates in t multiple times
• Choosing longer substrings unnecessarily
• Thinking it counts occurrences instead of substring