Minimum Window Substring in DSA C++ - Execution Trace

Concept Flow - Minimum Window Substring

Start with two pointers: left=0, right=0

↓

Expand right pointer to include chars

↓

Check if current window contains all target chars?

↓

Move right pointer forward

↓

Update minimum window if smaller

↓

Move left pointer forward

↓

Repeat until right reaches end

↓

Return minimum window substring

Use two pointers to expand and shrink a window over the string, tracking if it contains all target characters, updating the smallest valid window found.

Execution Sample

DSA C++

string minWindow(string s, string t) {
  unordered_map<char,int> need, window;
  for(char c : t) need[c]++;
  int left=0, right=0, valid=0;
  int start=0, len=INT_MAX;
  while(right < s.size()) {
    char c = s[right++];
    // update window
    // check valid
    // shrink window if valid
  }
  return len == INT_MAX ? "" : s.substr(start, len);
}

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

Execution Table

Step	Operation	Window Range [left,right)	Window Content	Valid Count	Minimum Window	Visual State
1	Initialize pointers	[0,0)		0	null	""
2	Expand right: add 'A'	[0,1)	A	1	null	A"
3	Expand right: add 'D'	[0,2)	AD	1	null	A -> D"
4	Expand right: add 'O'	[0,3)	ADO	1	null	A -> D -> O"
5	Expand right: add 'B'	[0,4)	ADOB	2	null	A -> D -> O -> B"
6	Expand right: add 'E'	[0,5)	ADOBE	2	null	A -> D -> O -> B -> E"
7	Expand right: add 'C'	[0,6)	ADOBEC	3	null	A -> D -> O -> B -> E -> C"
8	Window valid, try shrink left	[0,6)	ADOBEC	3	ADOBEC	A -> D -> O -> B -> E -> C"
9	Shrink left: remove 'A'	[1,6)	DOBEC	3	DOBEC	D -> O -> B -> E -> C"
10	Shrink left: remove 'D'	[2,6)	OBEC	2	DOBEC	O -> B -> E -> C"
11	Expand right: add 'O'	[2,7)	OBECO	2	DOBEC	O -> B -> E -> C -> O"
12	Expand right: add 'D'	[2,8)	OBECOD	3	DOBEC	O -> B -> E -> C -> O -> D"
13	Window valid, try shrink left	[2,8)	OBECOD	3	DOBEC	O -> B -> E -> C -> O -> D"
14	Shrink left: remove 'O'	[3,8)	BECOD	3	BECOD	B -> E -> C -> O -> D"
15	Shrink left: remove 'B'	[4,8)	ECOD	2	BECOD	E -> C -> O -> D"
16	Expand right: add 'E'	[4,9)	ECODE	2	BECOD	E -> C -> O -> D -> E"
17	Expand right: add 'B'	[4,10)	ECODEB	3	BECOD	E -> C -> O -> D -> E -> B"
18	Window valid, try shrink left	[4,10)	ECODEB	3	BECOD	E -> C -> O -> D -> E -> B"
19	Shrink left: remove 'E'	[5,10)	CODEB	3	CODEB	C -> O -> D -> E -> B"
20	Shrink left: remove 'C'	[6,10)	ODEB	2	CODEB	O -> D -> E -> B"
21	Expand right: add 'A'	[6,11)	ODEBA	2	CODEB	O -> D -> E -> B -> A"
22	Expand right: add 'N'	[6,12)	ODEBAN	2	CODEB	O -> D -> E -> B -> A -> N"
23	Expand right: add 'C'	[6,13)	ODEBANC	3	CODEB	O -> D -> E -> B -> A -> N -> C"
24	Window valid, try shrink left	[6,13)	ODEBANC	3	CODEB	O -> D -> E -> B -> A -> N -> C"
25	Shrink left: remove 'O'	[7,13)	DEBANC	3	CODEB	D -> E -> B -> A -> N -> C"
26	Shrink left: remove 'D'	[8,13)	EBANC	3	CODEB	E -> B -> A -> N -> C"
27	Shrink left: remove 'E'	[9,13)	BANC	3	BANC	B -> A -> N -> C
28	Shrink left: remove 'B'	[10,13)	ANC	2	BANC	A -> N -> C
29	End: right reached end	[10,13)	ANC	2	BANC	A -> N -> C

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

Variable Tracker

Variable	Start	After Step 7	After Step 14	After Step 19	After Step 27	Final
left	0	0	3	5	9	10
right	0	6	8	10	13	13
valid	0	3	3	3	3	2
min_len	inf	6	5	5	4	4
start	0	0	3	5	9	9

Key Moments - 3 Insights

Why do we move the left pointer only when the window is valid?

Because shrinking the window when it doesn't contain all target chars would lose needed chars. See steps 8 and 13 where we only shrink after confirming validity.

Why does the right pointer move first before checking validity?

We include the new character first to update the window counts before checking if the window is valid. See steps 2-7 where right moves and then validity is checked.

Why do we update the minimum window only when the window is valid?

Only valid windows contain all required chars, so only then can we consider updating the minimum. See step 8 where min window is first set.

Visual Quiz - 3 Questions

Look at the execution table at step 9. What is the window content and valid count?

A ADOBEC, valid=3

B DOBEC, valid=2

C DOBEC, valid=3

D DOBEC, valid=1

💡 Hint

Check the 'Window Content' and 'Valid Count' columns at step 9 in the execution_table.

At which step does the minimum window first get updated?

A Step 7

B Step 8

C Step 14

D Step 27

💡 Hint

Look for when 'Minimum Window' changes from null to a substring in the execution_table.

If the target string t had one less 'C', how would the valid count change at step 7?

A It would become 2

B It would remain 3

C It would become 4

D It would become 1

💡 Hint

Refer to variable_tracker and execution_table to see how valid count depends on required chars.

Concept Snapshot

Minimum Window Substring:
- Use two pointers (left, right) to create a sliding window.
- Expand right to include chars until window contains all target chars.
- Shrink left to minimize window while keeping it valid.
- Track counts of chars needed and in window.
- Return smallest valid window substring found.

Full Transcript

The Minimum Window Substring problem uses two pointers to slide over the string s. We expand the right pointer to include characters and update counts. When the window contains all characters from t, we try to shrink it from the left to find the smallest valid window. We keep track of the minimum window length and start index. The process continues until the right pointer reaches the end of s. The final result is the smallest substring containing all characters of t.

Practice

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

easy

A. Find the longest substring without repeating characters

B. Sort the characters of a string in ascending order

C. Count the number of substrings that contain a specific character

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

Solution

1. Step 1: Understand the problem statement

   The problem asks to find the smallest substring in a given string that contains all characters of another string, including duplicates.

2. Step 2: Compare with other substring problems

   Unlike longest substring or counting substrings, this problem focuses on minimum length substring covering all required characters.

3. Final Answer:

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

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 duplicate characters in target string
• Thinking it's about sorting or counting substrings

2. Which of the following C++ STL containers is most suitable to keep track of character counts in the Minimum Window Substring problem?

easy

A. std::unordered_map

B. std::vector<int>

C. std::stack<char>

D. std::queue<int>

Solution

1. Step 1: Identify the need for character frequency tracking

   We need to count how many times each character appears in the target string and track them in the window.

2. Step 2: Choose container supporting key-value pairs with fast access

   std::unordered_map allows mapping characters to counts with average O(1) access, ideal for this purpose.

3. Final Answer:

   std::unordered_map<char, int> -> Option A

4. Quick Check:

   Use unordered_map for char counts [OK]

Hint: Use unordered_map for fast char count lookup [OK]

Common Mistakes:

• Using stack or queue which don't support key-value mapping
• Using vector without mapping char to index
• Using map which is slower than unordered_map

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

std::string minWindow(std::string s, std::string t) {
    std::unordered_map dictT;
    for (char c : t) dictT[c]++;
    int required = dictT.size();
    int l = 0, r = 0, formed = 0;
    std::unordered_map windowCounts;
    int minLen = INT_MAX, minLeft = 0;
    while (r < s.size()) {
        char c = s[r];
        windowCounts[c]++;
        if (dictT.count(c) && windowCounts[c] == dictT[c]) formed++;
        while (l <= r && formed == required) {
            if (r - l + 1 < minLen) {
                minLen = r - l + 1;
                minLeft = l;
            }
            windowCounts[s[l]]--;
            if (dictT.count(s[l]) && windowCounts[s[l]] < dictT[s[l]]) formed--;
            l++;
        }
        r++;
    }
    return minLen == INT_MAX ? "" : s.substr(minLeft, minLen);
}

std::cout << minWindow("ADOBECODEBANC", "ABC") << std::endl;

medium

A. ADOBEC

B. BANC

C. CODEBA

D. ABC

Solution

1. Step 1: Understand the sliding window approach

   The code expands the right pointer to include characters and contracts the left pointer to find the smallest window containing all chars of t.

2. Step 2: Trace the window updates for s="ADOBECODEBANC" and t="ABC"

   The smallest substring containing 'A', 'B', and 'C' is "BANC" starting at index 9 with length 4.

3. Final Answer:

   BANC -> Option B

4. Quick Check:

   Minimum window substring = BANC [OK]

Hint: Trace window expansion and contraction carefully [OK]

Common Mistakes:

• Choosing first found substring instead of minimum
• Ignoring character counts and duplicates
• Confusing substring indices

4. Identify the bug in the following code snippet for Minimum Window Substring:

std::string minWindow(std::string s, std::string t) {
    std::unordered_map dictT;
    for (char c : t) dictT[c]++;
    int required = dictT.size();
    int l = 0, r = 0, formed = 0;
    std::unordered_map windowCounts;
    int minLen = INT_MAX, minLeft = 0;
    while (r < s.size()) {
        char c = s[r];
        windowCounts[c]++;
        if (dictT.count(c) && windowCounts[c] == dictT[c]) formed++;
        while (l <= r && formed == required) {
            if (r - l + 1 < minLen) {
                minLen = r - l + 1;
                minLeft = l;
            }
            windowCounts[s[l]]--;
            if (dictT.count(s[l]) && windowCounts[s[l]] < dictT[s[l]]) formed--;
            l++;
        }
        // Missing increment of r here
    }
    return minLen == INT_MAX ? "" : s.substr(minLeft, minLen);
}

medium

A. The right pointer 'r' is never incremented inside the loop

B. The function returns empty string always

C. The windowCounts map is not updated correctly

D. The variable 'formed' is never incremented

Solution

1. Step 1: Analyze the while loop controlling 'r'

   The loop uses 'r' to expand the window, but 'r' is never incremented inside the loop, causing an infinite loop.

2. Step 2: Identify missing increment

   Without 'r++' inside the loop, the window never expands, so the function cannot find the minimum window.

3. Final Answer:

   The right pointer 'r' is never incremented inside the loop -> Option A

4. Quick Check:

   Missing r++ causes infinite loop [OK]

Hint: Check loop variables increment carefully [OK]

Common Mistakes:

• Forgetting to increment pointers in loops
• Misusing condition checks for formed variable
• Not updating window counts correctly

5. Given strings s = "aabbccdd" and t = "abc", which of the following modifications to the standard Minimum Window Substring algorithm will correctly find the minimum window containing all characters of t even if t has duplicate characters like "aabc"?

hard

A. Use a set instead of a map to track characters

B. Ignore duplicates in t and only check unique characters

C. Use a frequency map for t and check counts exactly, including duplicates

D. Only check if all characters appear at least once, ignoring counts

Solution

1. Step 1: Understand the importance of duplicates in t

   If t contains duplicates, the algorithm must count how many times each character appears and ensure the window matches those counts.

2. Step 2: Modify frequency tracking to include exact counts

   Using a frequency map for t and comparing window counts exactly ensures duplicates are handled correctly.

3. Final Answer:

   Use a frequency map for t and check counts exactly, including duplicates -> Option C

4. Quick Check:

   Exact frequency counts handle duplicates [OK]

Hint: Count duplicates precisely using frequency maps [OK]

Common Mistakes:

• Ignoring duplicate characters in target string
• Using sets which lose count information
• Checking only presence, not frequency