Minimum Window Substring in DSA Javascript

Mental Model

Find the smallest part of a string that contains all characters of another string. We slide a window over the string, expanding and shrinking it to find the minimum size that fits all needed characters.

Analogy: Imagine you have a long shelf of books and a list of books you need. You want to find the shortest segment of the shelf that contains all the books on your list, moving your hands to grab and release books until you find the smallest group that works.

s: A B C D E F G H I J K L M N O P
window: [↑       ->          ]
need: {A:1, B:1, C:1}
have: {A:1, B:0, C:1}

The window moves right to include needed letters and left to shrink when all are included.

Dry Run Walkthrough

Input: s = "ADOBECODEBANC", t = "ABC"

Goal: Find the smallest substring in s that contains all characters A, B, and C

Step 1: Expand right pointer to include 'A'

Window: [A] DOBECODEBANC
have: {A:1}, need: {A:1, B:1, C:1}

Why: Start including characters to meet the need

Step 2: Expand right pointer to include 'D', 'O', 'B', 'E', 'C'

Window: [ADOBEC]ODEBANC
have: {A:1, B:1, C:1}, need: {A:1, B:1, C:1}

Why: Now window contains all needed characters

Step 3: Shrink left pointer to remove 'A' and check if window still valid

Window: [DOBEC]ODEBANC
have: {A:0, B:1, C:1}, need: {A:1, B:1, C:1}

Why: Removing 'A' breaks the requirement, so stop shrinking

Step 4: Expand right pointer to include 'O', 'D', 'E', 'B', 'A', 'N', 'C'

Window: DOBECODEBANC
have: {A:1, B:2, C:2}, need: {A:1, B:1, C:1}

Why: Try to find smaller valid window later

Step 5: Shrink left pointer to remove 'D', 'O', 'B', 'E', 'C', 'O', 'D', 'E', 'B'

Window: [BANC]
have: {A:1, B:1, C:1}, need: {A:1, B:1, C:1}

Why: Shrink to smallest valid window containing all needed characters

Result:

Window: B A N C -> "BANC" is the smallest substring containing A, B, and C

Annotated Code

DSA Javascript

class Solution {
  minWindow(s, t) {
    const need = new Map();
    for (const c of t) {
      need.set(c, (need.get(c) || 0) + 1);
    }
    let have = new Map();
    let haveCount = 0;
    let left = 0, minLen = Infinity, minStart = 0;

    for (let right = 0; right < s.length; right++) {
      const c = s[right];
      if (need.has(c)) {
        have.set(c, (have.get(c) || 0) + 1);
        if (have.get(c) === need.get(c)) {
          haveCount++;
        }
      }

      while (haveCount === need.size) {
        if (right - left + 1 < minLen) {
          minLen = right - left + 1;
          minStart = left;
        }
        const leftChar = s[left];
        if (need.has(leftChar)) {
          have.set(leftChar, have.get(leftChar) - 1);
          if (have.get(leftChar) < need.get(leftChar)) {
            haveCount--;
          }
        }
        left++;
      }
    }

    return minLen === Infinity ? "" : s.substring(minStart, minStart + minLen);
  }
}

// Driver code
const sol = new Solution();
const s = "ADOBECODEBANC";
const t = "ABC";
console.log(sol.minWindow(s, t));

for (const c of t) { need.set(c, (need.get(c) || 0) + 1); }

Count needed characters from t

if (need.has(c)) { have.set(c, (have.get(c) || 0) + 1); if (have.get(c) === need.get(c)) { haveCount++; } }

Add current char to have map and update count if requirement met

while (haveCount === need.size) { ... }

Shrink window from left while all needed chars are included

if (right - left + 1 < minLen) { minLen = right - left + 1; minStart = left; }

Update minimum window size and start index

if (need.has(leftChar)) { have.set(leftChar, have.get(leftChar) - 1); if (have.get(leftChar) < need.get(leftChar)) { haveCount--; } }

Remove left char from have map and update count if requirement broken

left++;

Move left pointer to shrink window

Output

BANC

Complexity Analysis

Time: O(n) because each character in s is visited at most twice by left and right pointers

Space: O(m) where m is the number of unique characters in t for the maps

vs Alternative: Naive approach checks all substrings leading to O(n^2) or worse; sliding window reduces to linear time

Edge Cases

t is empty

Returns empty string immediately

DSA Javascript

return minLen === Infinity ? "" : s.substring(minStart, minStart + minLen);

s is empty

Returns empty string as no window can be formed

DSA Javascript

return minLen === Infinity ? "" : s.substring(minStart, minStart + minLen);

t contains characters not in s

No valid window found, returns empty string

DSA Javascript

while (haveCount === need.size) { ... } ensures window only valid if all chars matched

When to Use This Pattern

When asked to find the smallest substring containing all characters of another string, use sliding window with two pointers to expand and shrink efficiently.

Common Mistakes

Mistake: Not updating haveCount correctly when characters are added or removed
Fix: Increase haveCount only when character count matches need; decrease when it falls below

Mistake: Shrinking window without checking if all needed characters are still included
Fix: Only shrink while haveCount equals need.size to maintain validity

Summary

Finds the smallest substring in s containing all characters of t.

Use when you need to find a minimal window covering all required elements.

The key is to expand right pointer to include needed chars and shrink left pointer to minimize window while keeping all chars.

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