Minimum Window Substring in DSA Typescript - Execution Trace

Concept Flow - Minimum Window Substring

Start with left=0, right=0

↓

Expand right pointer to include chars

↓

Check if window contains all target chars?

↓

Shrink from left to minimize

↓

Update min window if smaller

↓

Move left pointer right

↓

Repeat expand right

↓

End when right reaches string end

We move two pointers over the string: expand right to include needed chars, then shrink left to find smallest valid window.

Execution Sample

DSA Typescript

function minWindow(s: string, t: string): string {
  const need = new Map<string, number>();
  let left = 0, right = 0, count = t.length;
  let minLen = Infinity, start = 0;
  // ... sliding window logic
}

This code finds the smallest substring in s containing all chars of t using a sliding window.

Execution Table

Step	Operation	Window [left:right]	Chars Count Map	Count Needed	Min Window	Visual State
1	Initialize	left=0, right=0	{"A":1,"B":1,"C":1}	3	null	""
2	Expand right to include 'A'	[0:1]	{"A":0,"B":1,"C":1}	2	null	[A]"
3	Expand right to include 'D'	[0:2]	{"A":0,"B":1,"C":1}	2	null	[A D]"
4	Expand right to include 'O'	[0:3]	{"A":0,"B":1,"C":1}	2	null	[A D O]"
5	Expand right to include 'B'	[0:4]	{"A":0,"B":0,"C":1}	1	null	[A D O B]"
6	Expand right to include 'E'	[0:5]	{"A":0,"B":0,"C":1}	1	null	[A D O B E]"
7	Expand right to include 'C'	[0:6]	{"A":0,"B":0,"C":0}	0	null	[A D O B E C]"
8	Shrink left from 'A'	[1:6]	{"A":1,"B":0,"C":0}	1	"ADO BEC"	[D O B E C]"
9	Expand right to include 'O'	[1:7]	{"A":1,"B":0,"C":0}	1	"ADO BEC"	[D O B E C O]"
10	Expand right to include 'D'	[1:8]	{"A":1,"B":0,"C":0}	1	"ADO BEC"	[D O B E C O D]"
11	Shrink left from 'D'	[2:8]	{"A":1,"B":0,"C":0}	1	"ADO BEC"	[O B E C O D]"
12	Shrink left from 'O'	[3:8]	{"A":1,"B":0,"C":0}	1	"ADO BEC"	[B E C O D]"
13	Shrink left from 'B'	[4:8]	{"A":1,"B":1,"C":0}	2	"ADO BEC"	[E C O D]"
14	Expand right to include 'E'	[4:9]	{"A":1,"B":1,"C":0}	2	"ADO BEC"	[E C O D E]"
15	Expand right to include 'B'	[4:10]	{"A":1,"B":0,"C":0}	1	"ADO BEC"	[E C O D E B]"
16	Expand right to include 'A'	[4:11]	{"A":0,"B":0,"C":0}	0	"ADO BEC"	[E C O D E B A]"
17	Shrink left from 'E'	[5:11]	{"A":0,"B":0,"C":0}	0	"BANC"	[C O D E B A]"
18	Shrink left from 'C'	[6:11]	{"A":0,"B":0,"C":1}	1	"BANC"	[O D E B A]"
19	Expand right to include 'N'	[6:12]	{"A":0,"B":0,"C":1,"N":-1}	1	"BANC"	[O D E B A N]"
20	Expand right to include 'C'	[6:13]	{"A":0,"B":0,"C":0,"N":-1}	0	"BANC"	[O D E B A N C]"
21	Shrink left from 'O'	[7:13]	{"A":0,"B":0,"C":0,"N":-1}	0	"BANC"	[D E B A N C]"
22	Shrink left from 'D'	[8:13]	{"A":0,"B":0,"C":0,"N":-1}	0	"BANC"	[E B A N C]"
23	Shrink left from 'E'	[9:13]	{"A":0,"B":0,"C":0,"N":-1}	0	"BANC"	[B A N C]"
24	Shrink left from 'B'	[10:13]	{"A":0,"B":1,"C":0,"N":-1}	1	"BANC"	[A N C]"
25	End	[10:13]	{"A":0,"B":1,"C":0,"N":-1}	1	"BANC"	"Minimum window found: 'BANC'"

💡 Right pointer reached end of string; minimum window found.

Variable Tracker

Variable	Start	After Step 7	After Step 16	After Step 23	Final
left	0	0	4	9	10
right	0	6	11	13	13
count	3	0	0	0	1
minLen	Infinity	7	7	4	4
start	0	0	4	9	9

Key Moments - 3 Insights

Why do we shrink the window from the left only after count reaches zero?

Because count zero means the current window contains all needed chars. Shrinking before that would lose required chars, so we wait until count is zero (see steps 7 and 8).

Why does the count increase when we move left pointer past a needed char?

When we remove a needed char from the window by moving left, we increase count to indicate we need that char again to satisfy the condition (see step 13 and 24).

Why can the count map have negative values like for 'N'?

Negative values mean the window has more of that char than needed. This is okay and helps us know when we can shrink the window without losing required chars (see steps 19 and 20).

Visual Quiz - 3 Questions

Look at the execution table at step 7. What is the count value after including 'C'?

A 3

B 1

C 0

D 2

💡 Hint

Check the 'Count Needed' column at step 7 in the execution table.

At which step does the left pointer first move to shrink the window?

A Step 5

B Step 8

C Step 10

D Step 12

💡 Hint

Look for the first 'Shrink left' operation in the 'Operation' column.

If the target string t had an extra 'D', how would the count change after step 7?

A Count would be 1 instead of 0

B Count would be 0 as before

C Count would be -1

D Count would be 2

💡 Hint

Think about needing one more 'D' char to satisfy the target after step 7.

Concept Snapshot

Minimum Window Substring:
- Use two pointers (left, right) to create a sliding window.
- Expand right to include chars until all target chars are covered.
- Shrink left to minimize window while keeping all chars.
- Track counts of needed chars and update min window.
- Stop when right reaches string end.

Full Transcript

The Minimum Window Substring problem uses two pointers to find the smallest substring containing all characters of a target string. We start with both pointers at the beginning. We move the right pointer to include characters and update counts of needed characters. When the window contains all required characters (count reaches zero), we try to shrink the window from the left to find the smallest valid window. We update the minimum window length and start index whenever we find a smaller valid window. We continue this process until the right pointer reaches the end of the string. The final result is the smallest substring that contains all characters of the target string.

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