Minimum Window Substring in DSA Typescript

Mental Model

Find the smallest part of a big string that contains all characters of a smaller string. We slide a window over the big string and adjust it to keep all needed characters.

Analogy: Imagine you have a big bookshelf and want to find the shortest section that contains all your favorite books. You move your hands to cover parts of the shelf, expanding or shrinking the section until you find the smallest one with all favorites.

big string: [A] -> [D] -> [O] -> [B] -> [E] -> [C] -> [O] -> [D] -> [E] -> [B] -> [A] -> [N] -> [C] -> null
window: ↑               ↑
          left          right

Dry Run Walkthrough

Input: big string: "ADOBECODEBANC", small string: "ABC"

Goal: Find the smallest substring in big string containing all characters A, B, and C

Step 1: Expand right to 'C' (index 5), window "ADOBEC" valid, record len=6. Shrink left past 'A' to "DOBEC" invalid

A -> D -> O -> B -> E -> C
↑                 ↑
left             right

then
D -> O -> B -> E -> C
↑               ↑
left           right

Why: Expand to first valid window, attempt to shrink but removing A makes it invalid

Step 2: Expand right to second 'A' (index 10), window "DOBECODEBA" valid. Shrink past D, O, B, E, C to "ODEBA" invalid

D -> O -> B -> E -> C -> O -> D -> E -> B -> A
↑                                     ↑
left                                 right

then
O -> D -> E -> B -> A
↑             ↑
left         right

Why: Slide window forward to next valid, shrink maximally until invalid again

Step 3: Expand right to last 'C' (index 12), window "ODEBANC" valid

O -> D -> E -> B -> A -> N -> C
↑                   ↑
left               right

Why: Continue expanding to cover all required characters again

Step 4: Shrink left past O, D, E updating min to "EBANC" len=5 then "BANC" len=4. Past B makes invalid

B -> A -> N -> C
↑         ↑
left     right

Why: Shrink to find smallest valid window "BANC"

Result:

Minimum window substring is "BANC"

Annotated Code

DSA Typescript

class MinWindowSubstring {
  static minWindow(s: string, t: string): string {
    const need = new Map<string, number>();
    for (const c of t) {
      need.set(c, (need.get(c) ?? 0) + 1);
    }
    let left = 0, right = 0, valid = 0;
    const window = new Map<string, number>();
    let start = 0, minLen = Infinity;

    while (right < s.length) {
      const c = s[right];
      right++;
      if (need.has(c)) {
        window.set(c, (window.get(c) ?? 0) + 1);
        if (window.get(c) === need.get(c)) {
          valid++;
        }
      }

      while (valid === need.size) {
        if (right - left < minLen) {
          start = left;
          minLen = right - left;
        }
        const d = s[left];
        left++;
        if (need.has(d)) {
          if (window.get(d) === need.get(d)) {
            valid--;
          }
          window.set(d, window.get(d)! - 1);
        }
      }
    }

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

// Driver code
const bigString = "ADOBECODEBANC";
const smallString = "ABC";
const result = MinWindowSubstring.minWindow(bigString, smallString);
console.log(result);

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

Count needed characters from small string

while (right < s.length) { const c = s[right]; right++;

Expand right pointer to include new character

if (need.has(c)) { window.set(c, (window.get(c) ?? 0) + 1); if (window.get(c) === need.get(c)) { valid++; } }

Update window counts and check if character requirement met

while (valid === need.size) {

Try to shrink window while all required characters are included

if (right - left < minLen) { start = left; minLen = right - left; }

Update minimum window if current is smaller

const d = s[left]; left++; if (need.has(d)) { if (window.get(d) === need.get(d)) { valid--; } window.set(d, window.get(d)! - 1); }

Shrink from left and update counts and valid status

Output

BANC

Complexity Analysis

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

Space: O(m) where m is the number of unique characters in the small string for tracking counts

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

Edge Cases

Empty big string or small string

Returns empty string immediately as no window can be formed

DSA Typescript

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

Small string characters not in big string

No valid window found, returns empty string

DSA Typescript

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

Small string with repeated characters

Counts ensure window contains required number of each character

DSA Typescript

if (window.get(c) === need.get(c)) { valid++; }

When to Use This Pattern

When asked to find the smallest substring containing all characters of another string, use the sliding window pattern with two pointers and frequency maps to efficiently track and minimize the window.

Common Mistakes

Mistake: Not updating the valid count correctly when shrinking the window
Fix: Decrease valid only when the count of a needed character falls below required after shrinking

Mistake: Expanding and shrinking pointers incorrectly causing infinite loops
Fix: Always move right pointer forward in outer loop and left pointer forward inside inner loop when conditions met

Summary

Finds the smallest substring in a big string containing all characters of a smaller string.

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

The key is to expand the window until all needed characters are included, then shrink it to find the smallest valid window.

Practice

1. What is the main goal of the Minimum Window Substring problem?

easy

A. Sort characters of a string in ascending order

B. Find the smallest substring in a string that contains all characters of another string

C. Count the number of substrings containing a specific character

D. Find the longest substring without repeating characters

Solution

1. Step 1: Understand the problem statement

   The problem asks to find the smallest part of a string that has all characters from another string.

2. Step 2: Identify the goal

   The goal is to find the minimum length substring that contains all required characters, not just any substring.

3. Final Answer:

   Find the smallest substring in a string that contains all characters of another string -> Option B

4. Quick Check:

   Minimum window substring = smallest substring with all chars [OK]

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

Common Mistakes:

• Confusing with longest substring problems
• Ignoring the requirement to include all characters
• Thinking it's about sorting characters

2. Which of the following TypeScript code snippets correctly initializes a frequency map for characters in string t for the Minimum Window Substring problem?

easy

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

B. const freqMap = new Map(); for (const ch of t) { freqMap[ch] = freqMap[ch] + 1; }

C. const freqMap = new Map(); for (const ch of t) { freqMap.set(ch, (freqMap.get(ch) ?? 0) + 1); }

D. const freqMap = new Map(); for (const ch of t) { freqMap.set(ch, freqMap.get(ch) + 1); }

Solution

1. Step 1: Check correct Map usage in TypeScript

   const freqMap = new Map(); for (const ch of t) { freqMap.set(ch, (freqMap.get(ch) ?? 0) + 1); } uses Map with get and set methods and handles undefined with nullish coalescing (?? 0).

2. Step 2: Identify errors in other options

   const freqMap = {}; for (let i = 0; i < t.length; i++) { freqMap[t[i]] = freqMap[t[i]] + 1; } uses object but does not initialize counts, causing NaN. const freqMap = new Map(); for (const ch of t) { freqMap[ch] = freqMap[ch] + 1; } uses Map but accesses like object property, which is incorrect. const freqMap = new Map(); for (const ch of t) { freqMap.set(ch, freqMap.get(ch) + 1); } does not handle undefined before adding 1, causing NaN.

3. Final Answer:

   const freqMap = new Map(); for (const ch of t) { freqMap.set(ch, (freqMap.get(ch) ?? 0) + 1); } -> Option C

4. Quick Check:

   Use Map.get with ?? 0 to avoid undefined [OK]

Hint: Use Map.get with ?? 0 to safely increment counts [OK]

Common Mistakes:

• Accessing Map like an object property
• Not initializing counts before increment
• Using object without initializing keys

3. What will be the output of the following TypeScript code snippet for s = "ADOBECODEBANC" and t = "ABC"?

function minWindow(s: string, t: string): string {
  const freqMap = new Map();
  for (const ch of t) freqMap.set(ch, (freqMap.get(ch) ?? 0) + 1);
  let left = 0, right = 0, count = t.length, minLen = Infinity, start = 0;
  while (right < s.length) {
    const ch = s[right];
    if (freqMap.has(ch)) {
      freqMap.set(ch, freqMap.get(ch)! - 1);
      if (freqMap.get(ch)! >= 0) count--;
    }
    while (count === 0) {
      if (right - left + 1 < minLen) {
        minLen = right - left + 1;
        start = left;
      }
      const leftChar = s[left];
      if (freqMap.has(leftChar)) {
        freqMap.set(leftChar, freqMap.get(leftChar)! + 1);
        if (freqMap.get(leftChar)! > 0) count++;
      }
      left++;
    }
    right++;
  }
  return minLen === Infinity ? "" : s.substring(start, start + minLen);
}
console.log(minWindow(s, t));

medium

A. "BANC"

B. "ADOBEC"

C. "CODEBA"

D. "DOBECODEBA"

Solution

1. Step 1: Understand the sliding window approach

   The code uses two pointers expanding and shrinking the window to find the smallest substring containing all chars of t.

2. Step 2: Trace the code with given input

   The minimum window substring containing A, B, and C in s = "ADOBECODEBANC" and t = "ABC" is "BANC".

3. Final Answer:

   "BANC" -> Option A

4. Quick Check:

   Minimum window substring for "ABC" in "ADOBECODEBANC" is "BANC" [OK]

Hint: Use sliding window to shrink when all chars matched [OK]

Common Mistakes:

• Returning first found substring instead of minimum
• Not updating minimum length correctly
• Incorrectly increasing count when shrinking window

4. Identify the bug in the following TypeScript code snippet for Minimum Window Substring and select the fix:

function minWindow(s: string, t: string): string {
  const freqMap = new Map();
  for (const ch of t) freqMap.set(ch, (freqMap.get(ch) ?? 0) + 1);
  let left = 0, right = 0, count = t.length, minLen = Infinity, start = 0;
  while (right < s.length) {
    const ch = s[right];
    if (freqMap.has(ch)) {
      freqMap.set(ch, freqMap.get(ch)! - 1);
      if (freqMap.get(ch)! > 0) count--;
    }
    while (count === 0) {
      if (right - left + 1 < minLen) {
        minLen = right - left + 1;
        start = left;
      }
      const leftChar = s[left];
      if (freqMap.has(leftChar)) {
        freqMap.set(leftChar, freqMap.get(leftChar)! + 1);
        if (freqMap.get(leftChar)! > 0) count++;
      }
      left++;
    }
    right++;
  }
  return minLen === Infinity ? "" : s.substring(start, start + minLen);
}

medium

A. Change condition from if (freqMap.get(ch)! > 0) count--; to if (freqMap.get(ch)! >= 0) count--;

B. Initialize count with 0 instead of t.length

C. Remove the inner while loop

D. Change freqMap.set(ch, freqMap.get(ch)! - 1); to freqMap.set(ch, freqMap.get(ch)! + 1);

Solution

1. Step 1: Identify the condition for decreasing count

   The count should decrease when a needed character is found and its frequency is still >= 0, not > 0.

2. Step 2: Fix the condition

   Changing from > 0 to >= 0 ensures count decreases correctly when the character frequency reaches zero.

3. Final Answer:

   Change condition from if (freqMap.get(ch)! > 0) count--; to if (freqMap.get(ch)! >= 0) count--; -> Option A

4. Quick Check:

   Use >= 0 to count chars correctly [OK]

Hint: Use >= 0 when checking frequency to update count [OK]

Common Mistakes:

• Using > 0 causes missing valid matches
• Incorrect count initialization
• Removing inner loop breaks shrinking window

5. Given strings s = "aabbccdd" and t = "abc", which of the following substrings is the correct minimum window substring containing all characters of t? Consider that characters can appear multiple times in s but only once in t.

hard

A. "aabbc"

B. "abc"

C. "bcca"

D. "abbc"

Solution

1. Step 1: Understand character requirements

   String t requires one 'a', one 'b', and one 'c'. The substring must contain at least these once.

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

   "abbc" contains 'a', 'b', 'b', 'c' and is length 4. "abc" does not appear as a contiguous substring in s. "bcca" and "aabbc" are longer substrings.

3. Final Answer:

   "abbc" -> Option D

4. Quick Check:

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

Hint: Check substring length and character coverage carefully [OK]

Common Mistakes:

• Assuming "abc" substring exists exactly
• Ignoring repeated characters in s
• Choosing longer substrings unnecessarily