Minimum Window Substring in DSA Go - 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

Yes↓

Try to shrink window from left to minimize

↓

Update minimum window if smaller found

↓

Move left pointer right to shrink

↓

Repeat expand and shrink until right reaches end

↓

Return minimum window substring found or empty if none

Use two pointers to expand and shrink a window over the string, tracking characters to find the smallest substring containing all target characters.

Execution Sample

DSA Go

s := "ADOBECODEBANC"
t := "ABC"
left, right := 0, 0
minLen := len(s) + 1
count := map[byte]int{}
// Expand right, shrink left to find min window

This code finds the smallest substring in s containing all characters of t.

Execution Table

Step	Operation	Window [left:right]	Count Map	Contains All?	Min Window	Visual State
1	Initialize	[0:0]	{}	No	null	""
2	Expand right to include 'A'	[0:1]	{'A':1}	No	null	A"
3	Expand right to include 'D'	[0:2]	{'A':1,'D':1}	No	null	AD"
4	Expand right to include 'O'	[0:3]	{'A':1,'D':1,'O':1}	No	null	ADO"
5	Expand right to include 'B'	[0:4]	{'A':1,'D':1,'O':1,'B':1}	No	null	ADOB"
6	Expand right to include 'E'	[0:5]	{'A':1,'D':1,'O':1,'B':1,'E':1}	No	null	ADOBE"
7	Expand right to include 'C'	[0:6]	{'A':1,'D':1,'O':1,'B':1,'E':1,'C':1}	Yes	ADOBEC	ADOBEC"
8	Shrink left from 'A'	[1:6]	{'D':1,'O':1,'B':1,'E':1,'C':1}	No	ADOBEC	DOBEC"
9	Expand right to include 'O'	[1:7]	{'D':1,'O':2,'B':1,'E':1,'C':1}	No	ADOBEC	DOBECO"
10	Expand right to include 'D'	[1:8]	{'D':2,'O':2,'B':1,'E':1,'C':1}	No	ADOBEC	DOBECOD"
11	Expand right to include 'E'	[1:9]	{'D':2,'O':2,'B':1,'E':2,'C':1}	No	ADOBEC	DOBECODE"
12	Expand right to include 'B'	[1:10]	{'D':2,'O':2,'B':2,'E':2,'C':1}	No	ADOBEC	DOBECODEB"
13	Shrink left from 'D'	[2:10]	{'O':2,'B':2,'E':2,'C':1}	No	ADOBEC	OBECODEB"
14	Expand right to include 'A'	[2:11]	{'O':2,'B':2,'E':2,'C':1,'A':1}	Yes	ADOBEC	OBECODEBA"
15	Shrink left from 'O'	[3:11]	{'B':2,'E':2,'C':1,'A':1}	No	ADOBEC	BECODEBA"
16	Expand right to include 'N'	[3:12]	{'B':2,'E':2,'C':1,'A':1,'N':1}	No	ADOBEC	BECODEBAN"
17	Expand right to include 'C'	[3:13]	{'B':2,'E':2,'C':2,'A':1,'N':1}	Yes	ADOBEC	BECODEBANC"
18	Shrink left from 'B'	[4:13]	{'B':1,'E':2,'C':2,'A':1,'N':1}	Yes	ADOBEC	ECODEBANC"
19	Shrink left from 'E'	[5:13]	{'B':1,'E':1,'C':2,'A':1,'N':1}	Yes	ADOBEC	CODEBANC"
20	Shrink left from 'C'	[6:13]	{'B':1,'E':1,'C':1,'A':1,'N':1}	Yes	ADOBEC	ODEBANC"
21	Shrink left from 'O'	[7:13]	{'B':1,'E':1,'C':1,'A':1,'N':1}	Yes	ADOBEC	DEBANC"
22	Shrink left from 'D'	[8:13]	{'B':1,'E':1,'C':1,'A':1,'N':1}	Yes	EBANC	EBANC"
23	Shrink left from 'E'	[9:13]	{'B':1,'E':0,'C':1,'A':1,'N':1}	No	BANC	BANC"
24	Expand right pointer at end, stop	[9:13]	{'B':1,'E':0,'C':1,'A':1,'N':1}	No	BANC	BANC"

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

Variable Tracker

Variable	Start	After Step 7	After Step 12	After Step 17	After Step 22	Final
left	0	0	1	3	8	9
right	0	6	10	13	13	13
count map	{}	{'A':1,'D':1,'O':1,'B':1,'E':1,'C':1}	{'D':2,'O':2,'B':2,'E':2,'C':1}	{'B':2,'E':2,'C':2,'A':1,'N':1}	{'B':1,'E':1,'C':1,'A':1,'N':1}	{'B':1,'E':0,'C':1,'A':1,'N':1}
minLen	len(s)+1	6	6	6	5	4
minWindow	null	ADOBEC	ADOBEC	ADOBEC	EBANC	BANC

Key Moments - 3 Insights

Why do we shrink the window from the left only after confirming all target chars are included?

Because shrinking before having all required chars would lose needed characters. See execution_table rows 7 and 8: only after confirming 'Contains All?' is Yes do we try to shrink.

Why does the count map sometimes have characters with zero or missing counts?

Characters not in the current window or not needed are removed or zeroed. For example, after shrinking left in row 23, 'E' count becomes 0, indicating it's no longer in the window.

How do we know when to stop expanding the right pointer?

When the right pointer reaches the end of the string, as shown in the last row 24, we stop expanding and return the minimum window found.

Visual Quiz - 3 Questions

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

A DOBEC

B BANC

C ADOBEC

D null

💡 Hint

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

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

A Step 5

B Step 7

C Step 12

D Step 17

💡 Hint

Look at the 'Contains All?' column in execution_table to find the first 'Yes'.

If we did not shrink the window from the left, what would happen to the minimum window found?

A It would be the entire string

B It would be the first character only

C It would be the smallest substring

D It would be empty

💡 Hint

Refer to the 'Visual State' column and notice how shrinking reduces window size.

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 inside
- Shrink left to minimize window while keeping all chars
- Track counts of chars in window to check completeness
- Return smallest window found or empty if none

Full Transcript

Minimum Window Substring 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. When the window contains all target characters, we try to shrink it from the left to find a smaller valid window. We keep track of the minimum window found. 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 empty 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 number of times t appears as a substring 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 lexicographically smallest

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 problem exactly. Other options describe different tasks unrelated to the minimum window substring.

3. Final Answer:

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

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 about counting occurrences instead of substring
• Ignoring the need to include all characters of t

2. Which of the following Go code snippets correctly initializes a map to count characters for the Minimum Window Substring problem?

easy

A. counts := map[int]string{}

B. counts := make(map[rune]int)

C. counts := []int{}

D. counts := make([]rune, 0)

Solution

1. Step 1: Identify the correct data structure for counting characters

   We need a map with keys as characters (rune) and values as counts (int), so map[rune]int is correct.

2. Step 2: Check each option's type

   counts := make(map[rune]int) creates a map from rune to int, perfect for counting. Options B, C, and D use wrong types or slices, not suitable for counting characters.

3. Final Answer:

   counts := make(map[rune]int) -> Option B

4. Quick Check:

   Use map[rune]int for char counts [OK]

Hint: Use map[rune]int to count characters in Go [OK]

Common Mistakes:

• Using slice instead of map for counts
• Using wrong key or value types in map
• Not initializing the map before use

3. What will be the output of the following Go code snippet that tries to find the minimum window substring?

package main
import "fmt"
func main() {
    s := "ADOBECODEBANC"
    t := "ABC"
    result := minWindow(s, t)
    fmt.Println(result)
}

func minWindow(s, t string) string {
    need := make(map[rune]int)
    for _, c := range t {
        need[c]++
    }
    have := make(map[rune]int)
    left, right := 0, 0
    count := 0
    minLen := len(s) + 1
    start := 0
    for right < len(s) {
        c := rune(s[right])
        if need[c] > 0 {
            have[c]++
            if have[c] <= need[c] {
                count++
            }
        }
        for count == len(t) {
            if right-left+1 < minLen {
                minLen = right - left + 1
                start = left
            }
            leftChar := rune(s[left])
            if need[leftChar] > 0 {
                have[leftChar]--
                if have[leftChar] < need[leftChar] {
                    count--
                }
            }
            left++
        }
        right++
    }
    if minLen > len(s) {
        return ""
    }
    return s[start : start+minLen]
}

medium

A. "BANC"

B. "ADOBEC"

C. "CODEBA"

D. ""

Solution

1. Step 1: Understand the algorithm logic

   The code uses two pointers to find the smallest substring in s containing all chars of t. It updates the minimum length and start index when a valid window is found.

2. Step 2: Trace the example input

   For s = "ADOBECODEBANC" and t = "ABC", the minimum window substring containing 'A', 'B', and 'C' is "BANC".

3. Final Answer:

   "BANC" -> Option A

4. Quick Check:

   Minimum window substring for example = "BANC" [OK]

Hint: Trace pointers to find smallest valid substring [OK]

Common Mistakes:

• Not updating minimum length correctly
• Counting characters incorrectly
• Returning empty string when valid window exists

4. Identify the bug in this Go function for Minimum Window Substring and select the fix:

func minWindow(s, t string) string {
    need := make(map[rune]int)
    for _, c := range t {
        need[c]++
    }
    have := make(map[rune]int)
    left, right := 0, 0
    count := 0
    minLen := len(s) + 1
    start := 0
    for right < len(s) {
        c := rune(s[right])
        if need[c] > 0 {
            have[c]++
            if have[c] == need[c] {
                count++
            }
        }
        for count == len(t) {
            if right-left+1 < minLen {
                minLen = right - left + 1
                start = left
            }
            leftChar := rune(s[left])
            if need[leftChar] > 0 {
                have[leftChar]--
                if have[leftChar] < need[leftChar] {
                    count--
                }
            }
            left++
        }
        right++
    }
    if minLen > len(s) {
        return ""
    }
    return s[start : start+minLen]
}

medium

A. Initialize count to 1 instead of 0

B. Remove the if need[c] > 0 check inside the loop

C. Use for right <= len(s) instead of right < len(s)

D. Change count == len(t) to count == len(need) in the inner loop condition

Solution

1. Step 1: Understand the role of count and need map

   The variable count tracks how many required characters are matched. The map need holds unique characters from t. Using len(t) counts total characters including duplicates, which is incorrect.

2. Step 2: Identify the correct condition for a valid window

   The condition should check if count equals the number of unique characters needed, which is len(need). Changing the condition fixes the bug.

3. Final Answer:

   Change count == len(t) to count == len(need) in the inner loop condition -> Option D

4. Quick Check:

   Use unique char count for window check [OK]

Hint: Match count with unique chars, not total chars [OK]

Common Mistakes:

• Confusing total chars with unique chars count
• Incorrect loop boundary causing index errors
• Ignoring character presence check before counting

5. Given strings s = "aabbccdd" and t = "abc", what is the minimum window substring that contains all characters of t at least once? Consider the following approach: - Use two pointers to slide over s - Count characters needed from t - Shrink window when all chars matched What is the correct minimum window substring?

hard

A. "abbc"

B. "abc"

C. "aabbc"

D. "bcca"

Solution

1. Step 1: Identify characters needed and their counts

   Characters needed are 'a', 'b', and 'c'. We want the smallest substring containing at least one of each.

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

   Checking substrings: "abbc" (positions 1-4) contains 'a', 'b', 'c' and is smaller than "aabbc" or others. "abc" does not appear as continuous substring. "bcca" is not in order and does not appear as substring.

3. Final Answer:

   "abbc" -> Option A

4. Quick Check:

   Smallest substring with all chars = "abbc" [OK]

Hint: Slide window and shrink when all chars matched [OK]

Common Mistakes:

• Assuming substring must be exact order of t
• Choosing longer substrings unnecessarily
• Ignoring repeated characters in s