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 forward

↓

Update minimum window if smaller

↓

Repeat until right reaches end

↓

Return smallest window found or empty if none

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 s = "ADOBECODEBANC";
string t = "ABC";
// Find minimum window in s containing all chars of t

Find the smallest substring in s that contains all characters from t.

Execution Table

Step	Operation	Left Pointer	Right Pointer	Window Substring	Window Counts	Contains All Target?	Minimum Window So Far
1	Initialize pointers and counts	0	0	"A"	{"A":1}	No	None
2	Expand right to include 'D'	0	1	"AD"	{"A":1,"D":1}	No	None
3	Expand right to include 'O'	0	2	"ADO"	{"A":1,"D":1,"O":1}	No	None
4	Expand right to include 'B'	0	3	"ADOB"	{"A":1,"D":1,"O":1,"B":1}	No	None
5	Expand right to include 'E'	0	4	"ADOBE"	{"A":1,"D":1,"O":1,"B":1,"E":1}	No	None
6	Expand right to include 'C'	0	5	"ADOBEC"	{"A":1,"D":1,"O":1,"B":1,"E":1,"C":1}	Yes	"ADOBEC"
7	Shrink left to remove 'A'	1	5	"DOBEC"	{"D":1,"O":1,"B":1,"E":1,"C":1}	No	"ADOBEC"
8	Expand right to include 'O'	1	6	"DOBECO"	{"D":1,"O":2,"B":1,"E":1,"C":1}	No	"ADOBEC"
9	Expand right to include 'D'	1	7	"DOBECOD"	{"D":2,"O":2,"B":1,"E":1,"C":1}	No	"ADOBEC"
10	Expand right to include 'E'	1	8	"DOBECODE"	{"D":2,"O":2,"B":1,"E":2,"C":1}	No	"ADOBEC"
11	Expand right to include 'B'	1	9	"DOBECODEB"	{"D":2,"O":2,"B":2,"E":2,"C":1}	Yes	"ADOBEC"
12	Shrink left to remove 'D'	2	9	"OBECODEB"	{"O":2,"B":2,"E":2,"C":1,"D":1}	Yes	"ADOBEC"
13	Shrink left to remove 'O'	3	9	"BECODEB"	{"B":2,"E":2,"C":1,"D":1,"O":1}	Yes	"ADOBEC"
14	Shrink left to remove 'B'	4	9	"ECODEB"	{"E":2,"C":1,"D":1,"O":1,"B":1}	Yes	"ADOBEC"
15	Shrink left to remove 'E'	5	9	"CODEB"	{"C":1,"D":1,"O":1,"B":1,"E":1}	Yes	"ADOBEC"
16	Shrink left to remove 'C'	6	9	"ODEB"	{"O":1,"D":1,"E":1,"B":1}	No	"ADOBEC"
17	Expand right to include 'A'	6	10	"ODEBA"	{"O":1,"D":1,"E":1,"B":1,"A":1}	No	"ADOBEC"
18	Expand right to include 'N'	6	11	"ODEBAN"	{"O":1,"D":1,"E":1,"B":1,"A":1,"N":1}	No	"ADOBEC"
19	Expand right to include 'C'	6	12	"ODEBANC"	{"O":1,"D":1,"E":1,"B":1,"A":1,"N":1,"C":1}	Yes	"ADOBEC"
20	Shrink left to remove 'O'	7	12	"DEBANC"	{"D":1,"E":1,"B":1,"A":1,"N":1,"C":1}	Yes	"ADOBEC"
21	Shrink left to remove 'D'	8	12	"EBANC"	{"E":1,"B":1,"A":1,"N":1,"C":1}	Yes	"ADOBEC"
22	Shrink left to remove 'E'	9	12	"BANC"	{"B":1,"A":1,"N":1,"C":1}	Yes	"ADOBEC"
23	Shrink left to remove 'B'	10	12	"ANC"	{"A":1,"N":1,"C":1}	No	"ADOBEC"
24	End: right pointer reached end	10	12	"ANC"	{"A":1,"N":1,"C":1}	No	"BANC"

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

Variable Tracker

Variable	Start	After Step 6	After Step 11	After Step 15	After Step 19	After Step 22	Final
left	0	0	1	5	6	9	10
right	0	5	9	9	12	12	12
window_counts	{}	{"A":1,"D":1,"O":1,"B":1,"E":1,"C":1}	{"D":2,"O":2,"B":2,"E":2,"C":1}	{"C":1,"D":1,"O":1,"B":1,"E":1}	{"O":1,"D":1,"E":1,"B":1,"A":1,"N":1,"C":1}	{"B":1,"A":1,"N":1,"C":1}	{"B":1,"A":1,"N":1,"C":1}
min_window	None	"ADOBEC"	"ADOBEC"	"ADOBEC"	"ADOBEC"	"ADOBEC"	"BANC"

Key Moments - 3 Insights

Why do we move the left pointer only after the window contains all target characters?

Because shrinking the window before it contains all target characters would lose required characters, as shown in steps 6 and 7 where the window first contains all chars, then we try to shrink.

Why do we update the minimum window only when the window contains all target characters?

Because only then the window is valid. For example, at step 6 the window first contains all target chars and we record it. Before that, the window is invalid and not considered.

Why does the right pointer move forward even if the window already contains all target characters?

To find potentially smaller windows by expanding and then shrinking from the left, as seen between steps 11 to 19 where right pointer moves to find better windows.

Visual Quiz - 3 Questions

Look at the execution table, what is the window substring at step 15?

A "ECODEB"

B "BECODEB"

C "CODEB"

D "DOBECODEB"

💡 Hint

Check the 'Window Substring' column at step 15 in the execution table.

At which step does the window first contain all target characters?

A Step 5

B Step 6

C Step 11

D Step 19

💡 Hint

Look for the first 'Yes' in the 'Contains All Target?' column.

If the target string was "AB", how would the minimum window change compared to the final result?

A "BA"

B "BANC" (same as original)

C "BANC"

D "AN"

💡 Hint

With fewer target chars, the minimum window would be smaller; check how window shrinks in the execution table.

Concept Snapshot

Minimum Window Substring:
- Use two pointers (left, right) to scan string
- Expand right to include chars until all targets found
- Shrink left to minimize window while valid
- Track counts of chars in window
- Update minimum window when valid
- Return smallest valid substring or empty if none

Full Transcript

The Minimum Window Substring problem is solved by using two pointers to create a sliding window over the input string. We expand the right pointer to include characters until the window contains all characters from the target string. Then, we try to shrink the window from the left to find the smallest valid window. We keep track of character counts in the current window and update the minimum window found whenever the window is valid. The process continues until the right pointer reaches the end of the string. The final result is the smallest substring containing all target characters or an empty string if none exists.

Practice

1. What does the "Minimum Window Substring" problem ask you to find given two strings s and t?

easy

A. The substring of s that is exactly equal to t

B. The longest substring in s that does not contain any character of t

C. The number of times t appears in s

D. The smallest substring in s that contains all characters of t

Solution

1. Step 1: Understand the problem goal

   The problem asks to find the smallest part of string s that includes every character from string t at least once.

2. Step 2: Compare options with the problem goal

   The smallest substring in s that contains all characters of t matches the goal exactly. The longest substring without characters from t, the count of t appearances, or exact equality to t describe unrelated problems.

3. Final Answer:

   The smallest substring in s that contains all characters of t -> Option D

4. Quick Check:

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

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

Common Mistakes:

• Confusing minimum window with longest substring
• Thinking it counts occurrences instead of covering characters
• Assuming substring must be equal to t

2. Which of the following C# code snippets correctly initializes a dictionary to count characters of string t for the Minimum Window Substring problem?

easy

A. var dict = new Dictionary(); foreach (var c in t) { dict.Add(c, 1); }

B. var dict = new Dictionary(); foreach (var c in t) { dict[c] = dict.GetValueOrDefault(c, 0) + 1; }

C. var dict = new Dictionary(); foreach (var c in t) { dict.Add(c, 1); }

D. var dict = new Dictionary(); foreach (var c in t) { dict[c] += 1; }

Solution

1. Step 1: Check dictionary type and initialization

   Dictionary<char, int> is correct for counting characters. Dictionary<int, char> uses wrong types. Adding keys with Add fails on duplicates in t. Incrementing with += on uninitialized keys causes exceptions.

2. Step 2: Verify counting logic

   GetValueOrDefault(c, 0) + 1 safely handles missing keys and increments correctly for duplicates. Add(c, 1) throws on duplicates. dict[c] += 1 throws KeyNotFoundException on first occurrence.

3. Final Answer:

   var dict = new Dictionary<char, int>(); foreach (var c in t) { dict[c] = dict.GetValueOrDefault(c, 0) + 1; } -> Option B

4. Quick Check:

   Correct dictionary initialization and counting = var dict = new Dictionary(); foreach (var c in t) { dict[c] = dict.GetValueOrDefault(c, 0) + 1; } [OK]

Hint: Use GetValueOrDefault to safely increment dictionary counts [OK]

Common Mistakes:

• Using wrong dictionary key/value types
• Adding duplicate keys without checking
• Incrementing dictionary values without initialization

3. What is the output of the following C# code snippet for the Minimum Window Substring problem?

string s = "ADOBECODEBANC";
string t = "ABC";
string result = MinWindow(s, t);
Console.WriteLine(result);

string MinWindow(string s, string t) {
    var dictT = new Dictionary();
    foreach (var c in t) dictT[c] = dictT.GetValueOrDefault(c, 0) + 1;
    int required = dictT.Count;
    int l = 0, r = 0, formed = 0;
    var windowCounts = new Dictionary();
    int[] ans = {-1, 0, 0};
    while (r < s.Length) {
        char c = s[r];
        windowCounts[c] = windowCounts.GetValueOrDefault(c, 0) + 1;
        if (dictT.ContainsKey(c) && windowCounts[c] == dictT[c]) formed++;
        while (l <= r && formed == required) {
            c = s[l];
            if (ans[0] == -1 || r - l + 1 < ans[0]) {
                ans[0] = r - l + 1;
                ans[1] = l;
                ans[2] = r;
            }
            windowCounts[c]--;
            if (dictT.ContainsKey(c) && windowCounts[c] < dictT[c]) formed--;
            l++;
        }
        r++;
    }
    return ans[0] == -1 ? "" : s.Substring(ans[1], ans[0]);
}

medium

A. "CODEBA"

B. "ADOBEC"

C. "BANC"

D. "ABC"

Solution

1. Step 1: Understand the sliding window logic

   The code uses two pointers to find the smallest substring in s containing all chars of t. It expands right pointer r to include chars and moves left pointer l to minimize window while keeping all required chars.

2. Step 2: Trace the example input

   For s = "ADOBECODEBANC" and t = "ABC", the minimum window substring containing 'A', 'B', and 'C' is "BANC" starting at index 9 with length 4.

3. Final Answer:

   "BANC" -> Option C

4. Quick Check:

   Minimum window substring for given input = "BANC" [OK]

Hint: Use sliding window to track counts and minimize substring [OK]

Common Mistakes:

• Returning first found substring instead of minimum
• Not updating minimum window when smaller found
• Incorrectly updating counts causing wrong formed count

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

string MinWindow(string s, string t) {
    var dictT = new Dictionary();
    foreach (var c in t) dictT[c] = dictT.GetValueOrDefault(c, 0) + 1;
    int required = dictT.Count;
    int l = 0, r = 0, formed = 0;
    var windowCounts = new Dictionary();
    int[] ans = {-1, 0, 0};
    while (r < s.Length) {
        char c = s[r];
        windowCounts[c] = windowCounts.GetValueOrDefault(c, 0) + 1;
        if (dictT.ContainsKey(c) && windowCounts[c] == dictT[c]) formed++;
        while (l <= r && formed == required) {
            c = s[l];
            if (ans[0] == -1 || r - l + 1 < ans[0]) {
                ans[0] = r - l + 1;
                ans[1] = l;
                ans[2] = r;
            }
            windowCounts[c]--;
            if (dictT.ContainsKey(c) && windowCounts[c] <= dictT[c]) formed--;
            l++;
        }
        r++;
    }
    return ans[0] == -1 ? "" : s.Substring(ans[1], ans[0]);
}

medium

A. Change condition from windowCounts[c] <= dictT[c] to windowCounts[c] < dictT[c] when decreasing formed

B. Initialize formed to 1 instead of 0

C. Remove the inner while loop to avoid infinite loop

D. Change ans array size to 4 elements

Solution

1. Step 1: Analyze the condition for decreasing formed count

   The bug is in the line if (dictT.ContainsKey(c) && windowCounts[c] <= dictT[c]) formed--;. Using <= causes formed to decrease even when counts are equal, prematurely reducing formed.

2. Step 2: Correct the condition to strictly less than

   Changing condition to windowCounts[c] < dictT[c] ensures formed decreases only when count falls below required, fixing the bug.

3. Final Answer:

   Change condition from windowCounts[c] <= dictT[c] to windowCounts[c] < dictT[c] when decreasing formed -> Option A

4. Quick Check:

   Strict less than fixes formed decrement bug [OK]

Hint: Use < than, not <=, when checking counts to reduce formed [OK]

Common Mistakes:

• Using <= instead of < causing wrong formed count
• Incorrect initialization of formed variable
• Removing inner loop causing incorrect window shrinking

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

hard

A. "aabbcc"

B. "abc"

C. "bcca"

D. "abbc"

Solution

1. Step 1: Identify required characters and counts

   String t requires one 'a', one 'b', and one 'c'. We need the smallest substring in s containing at least one of each.

2. Step 2: Find minimum substring in s covering all required chars

   Checking substrings: "aabbcc" (positions 0 to 5) contains 'a', 'b', and 'c' at least once each and is the smallest substring covering all required characters. "abbc" (positions 1 to 4) misses 'c' at position 4 (which is 'b'), so it does not contain 'c'. "abc" does not appear consecutively. "bcca" is not a substring in order. So "aabbcc" is the smallest valid window.

3. Final Answer:

   "aabbcc" -> Option A

4. Quick Check:

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

Hint: Check all substrings covering t chars, pick shortest [OK]

Common Mistakes:

• Choosing substring missing one required character
• Picking substring with correct chars but longer length
• Ignoring character counts in t