Minimum Window Substring in DSA Javascript - Execution Trace

Concept Flow - Minimum Window Substring

Start

↓

Initialize frequency map of target chars

↓

Set two pointers: left=0, right=0

↓

Expand right pointer to include chars

↓

Check if current window contains all target chars?

↓

Expand right

↓

Repeat until right reaches end

↓

Return smallest window found or empty string

The flow shows how two pointers expand and shrink a window over the string to find the smallest substring containing all target characters.

Execution Sample

DSA Javascript

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

This code finds the smallest substring in s that contains all characters of t using a sliding window with two pointers.

Execution Table

Step	Operation	Left Pointer	Right Pointer	Count (chars needed)	Frequency Map State	Current Window	Min Window Found
1	Initialize frequency map for t='ABC'	0	0	3	{"A":1,"B":1,"C":1}	""	""
2	Expand right: include 'A'	0	0	2	{"A":0,"B":1,"C":1}	"A"	""
3	Expand right: include 'D'	0	1	2	{"A":0,"B":1,"C":1}	"AD"	""
4	Expand right: include 'O'	0	2	2	{"A":0,"B":1,"C":1}	"ADO"	""
5	Expand right: include 'B'	0	3	1	{"A":0,"B":0,"C":1}	"ADOB"	""
6	Expand right: include 'E'	0	4	1	{"A":0,"B":0,"C":1}	"ADOBE"	""
7	Expand right: include 'C'	0	5	0	{"A":0,"B":0,"C":0}	"ADOBEC"	"ADOBEC"
8	Shrink left: remove 'A'	1	5	1	{"A":1,"B":0,"C":0}	"DOBEC"	"ADOBEC"
9	Expand right: include 'O'	1	6	1	{"A":1,"B":0,"C":0}	"DOBECO"	"ADOBEC"
10	Expand right: include 'D'	1	7	1	{"A":1,"B":0,"C":0}	"DOBECOD"	"ADOBEC"
11	Expand right: include 'E'	1	8	1	{"A":1,"B":0,"C":0}	"DOBECODE"	"ADOBEC"
12	Expand right: include 'B'	1	9	1	{"A":1,"B":-1,"C":0}	"DOBECODEB"	"ADOBEC"
13	Expand right: include 'A'	1	10	0	{"A":0,"B":-1,"C":0}	"DOBECODEBA"	"ADOBEC"
14	Shrink left: remove 'D'	2	10	0	{"A":0,"B":-1,"C":0}	"OBECODEBA"	"ADOBEC"
15	Shrink left: remove 'O'	3	10	0	{"A":0,"B":-1,"C":0}	"BECODEBA"	"ADOBEC"
16	Shrink left: remove 'B'	4	10	0	{"A":0,"B":0,"C":0}	"ECODEBA"	"ADOBEC"
17	Shrink left: remove 'E'	5	10	0	{"A":0,"B":0,"C":0}	"CODEBA"	"ADOBEC"
18	Shrink left: remove 'C'	6	10	1	{"A":0,"B":0,"C":1}	"ODEBA"	"ADOBEC"
19	Expand right: include 'N'	6	11	1	{"A":0,"B":0,"C":1}	"ODEBAN"	"ADOBEC"
20	Expand right: include 'C'	6	12	0	{"A":0,"B":0,"C":0}	"ODEBANC"	"ADOBEC"
21	Shrink left: remove 'O'	7	12	0	{"A":0,"B":0,"C":0}	"DEBANC"	"ADOBEC"
22	Shrink left: remove 'D'	8	12	0	{"A":0,"B":0,"C":0}	"EBANC"	"ADOBEC"
23	Shrink left: remove 'E'	9	12	0	{"A":0,"B":0,"C":0}	"BANC"	"BANC"
24	Shrink left: remove 'B'	10	12	1	{"A":0,"B":1,"C":0}	"ANC"	"BANC"
25	End: right reached end of s	10	12	1	{"A":0,"B":1,"C":0}	"ANC"	"BANC"

💡 Right pointer reached end of string; smallest window found is 'BANC'

Variable Tracker

Variable	Start	After Step 2	After Step 7	After Step 8	After Step 12	After Step 16	After Step 23	Final
left	0	0	0	1	1	4	9	10
right	0	0	5	5	9	10	12	12
count	3	2	0	1	1	0	0	1
minLen	Infinity	Infinity	6	6	6	6	4	4
start	0	0	0	0	0	0	9	9
frequency map	{"A":1,"B":1,"C":1}	{"A":0,"B":1,"C":1}	{"A":0,"B":0,"C":0}	{"A":1,"B":0,"C":0}	{"A":1,"B":-1,"C":0}	{"A":0,"B":0,"C":0}	{"A":0,"B":0,"C":0}	{"A":0,"B":1,"C":0}

Key Moments - 3 Insights

Why do we decrease count only when need.get(char) > 0 during expansion?

Because count tracks how many needed characters are still missing. If need.get(char) <= 0, it means we have extra of that char, so count should not decrease. See steps 2 and 12 in execution_table.

Why do we increase count when moving left pointer if need.get(char) > 0?

When shrinking the window, if we remove a needed character (frequency goes above zero), it means the window no longer contains all required chars, so count increases. See step 15 and 24.

Why do we update minLen and start only when count == 0?

Because count == 0 means current window contains all target chars. Only then can we check if this window is smaller than previous best. See steps 7, 23.

Visual Quiz - 3 Questions

Look at the execution_table at step 7, what is the current window substring?

A "ADOB"

B "DOBEC"

C "ADOBEC"

D "BEC"

💡 Hint

Check the 'Current Window' column at step 7 in execution_table.

At which step does the count variable first become zero?

A Step 7

B Step 12

C Step 5

D Step 16

💡 Hint

Look at the 'Count' column in execution_table and find when it reaches 0 first.

If the target string t was "AB", how would the initial count value change?

A It would be 3

B It would be 2

C It would be 1

D It would be 0

💡 Hint

Count starts as the length of t, see variable_tracker 'count' start value.

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 needed chars with a frequency map and count.
- Return smallest window substring or empty if none found.

Full Transcript

The Minimum Window Substring problem finds the smallest substring in a string s that contains all characters of another string t. We use two pointers, left and right, to create a sliding window over s. We keep a frequency map of characters needed from t and a count of how many are still missing. We expand the right pointer to include characters, decreasing count when a needed character is found. When count reaches zero, the window contains all needed characters, so we try to shrink it from the left to find the smallest valid window. We update the minimum window length and start position accordingly. This process continues until the right pointer reaches the end of s. The final result is the smallest substring found or an empty string if no valid window exists.

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