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

↓

Update min window if smaller

↓

Move left pointer to shrink window

↓

Repeat until right reaches end

↓

Return smallest window found or empty

We use two pointers to slide over the string, expanding right to include needed chars, then shrinking left to find the smallest valid window.

Execution Sample

DSA Rust

fn min_window(s: &str, t: &str) -> String {
    // sliding window approach
}

Find the smallest substring in s containing all chars of t.

Execution Table

Step	Operation	Left Pointer	Right Pointer	Window Substring	Frequency Map State	Valid Count	Min Window
1	Initialize frequency map for t='ABC'	-	-	-	{"A":1,"B":1,"C":1}	0	""
2	Expand right to include 'A'	0	0	"A"	{"A":0,"B":1,"C":1}	1	""
3	Expand right to include 'D'	0	1	"AD"	{"A":0,"B":1,"C":1}	1	""
4	Expand right to include 'O'	0	2	"ADO"	{"A":0,"B":1,"C":1}	1	""
5	Expand right to include 'B'	0	3	"ADOB"	{"A":0,"B":0,"C":1}	2	""
6	Expand right to include 'E'	0	4	"ADOBE"	{"A":0,"B":0,"C":1}	2	""
7	Expand right to include 'C'	0	5	"ADOBEC"	{"A":0,"B":0,"C":0}	3	"ADOBEC"
8	Try shrink from left: remove 'A'	1	5	"DOBEC"	{"A":1,"B":0,"C":0}	2	"ADOBEC"
9	Expand right to include 'O'	1	6	"DOBECO"	{"A":1,"B":0,"C":0}	2	"ADOBEC"
10	Expand right to include 'D'	1	7	"DOBECOD"	{"A":1,"B":0,"C":0}	2	"ADOBEC"
11	Expand right to include 'E'	1	8	"DOBECODE"	{"A":1,"B":0,"C":0}	2	"ADOBEC"
12	Expand right to include 'B'	1	9	"DOBECODEB"	{"A":1,"B":-1,"C":0}	3	"ADOBEC"
13	Try shrink from left: remove 'D'	2	9	"OBECODEB"	{"A":1,"B":-1,"C":0}	3	"ADOBEC"
14	Try shrink from left: remove 'O'	3	9	"BECODEB"	{"A":1,"B":-1,"C":0}	3	"ADOBEC"
15	Try shrink from left: remove 'B'	4	9	"ECODEB"	{"A":1,"B":0,"C":0}	3	"BECODEB"
16	Try shrink from left: remove 'E'	5	9	"CODEB"	{"A":1,"B":0,"C":0}	3	"BECODEB"
17	Try shrink from left: remove 'C'	6	9	"ODEB"	{"A":1,"B":0,"C":1}	2	"BECODEB"
18	Expand right to include 'A'	6	10	"ODEBA"	{"A":0,"B":0,"C":1}	3	"BECODEB"
19	Try shrink from left: remove 'O'	7	10	"DEBA"	{"A":0,"B":0,"C":1}	3	"BECODEB"
20	Try shrink from left: remove 'D'	8	10	"EBA"	{"A":0,"B":0,"C":1}	3	"BECODEB"
21	Try shrink from left: remove 'E'	9	10	"BA"	{"A":0,"B":0,"C":1}	3	"BECODEB"
22	Try shrink from left: remove 'B'	10	10	"A"	{"A":0,"B":1,"C":1}	2	"BECODEB"
23	Expand right to include 'N'	10	11	"AN"	{"A":0,"B":1,"C":1}	2	"BECODEB"
24	Expand right to include 'C'	10	12	"ANC"	{"A":0,"B":1,"C":0}	3	"BANC"
25	Try shrink from left: remove 'A'	11	12	"NC"	{"A":1,"B":1,"C":0}	2	"BANC"
26	Right pointer reached end, stop	11	12	"NC"	{"A":1,"B":1,"C":0}	2	"BANC"

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

Variable Tracker

Variable	Start	After Step 7	After Step 8	After Step 15	After Step 18	After Step 24	Final
left	0	0	1	5	6	11	11
right	0	5	5	9	10	12	12
valid_count	0	3	2	3	3	3	2
min_window	""	"ADOBEC"	"ADOBEC"	"BECODEB"	"BECODEB"	"BANC"	"BANC"
frequency_map	{"A":1,"B":1,"C":1}	{"A":0,"B":0,"C":0}	{"A":1,"B":0,"C":0}	{"A":1,"B":0,"C":0}	{"A":0,"B":0,"C":1}	{"A":1,"B":1,"C":0}	{"A":1,"B":1,"C":0}

Key Moments - 3 Insights

Why do we increase the frequency count when moving left pointer?

When shrinking the window from the left (see steps 8 and 15), we remove a character from the window, so we increase its frequency in the map to reflect it's missing again. This helps track if the window still contains all needed chars.

Why does valid_count decrease when frequency map value becomes positive?

valid_count counts how many required chars are fully included. When frequency for a char becomes positive (meaning missing), valid_count decreases (step 8), indicating the window no longer contains all required chars.

Why do we keep expanding right pointer even after finding a valid window?

Expanding right pointer (steps 9-12) tries to find a smaller valid window by including more chars and then shrinking from left. This ensures we find the minimum window, not just the first valid one.

Visual Quiz - 3 Questions

Look at the execution table at step 7, what is the valid_count?

A 1

B 3

C 2

D 0

💡 Hint

Check the 'Valid Count' column at step 7 in the execution_table.

At which step does the min_window first get updated to "BECODEB"?

A Step 15

B Step 18

C Step 8

D Step 24

💡 Hint

Look at the 'Min Window' column in execution_table and find when it changes to "BECODEB".

If the target string t was "AB", how would valid_count change at step 7?

A It would be 1

B It would be 3

C It would be 2

D It would be 0

💡 Hint

Consider frequency map and valid_count logic for only 'A' and 'B' at step 7.

Concept Snapshot

Minimum Window Substring:
- Use two pointers (left, right) to slide over string s
- Expand right to include chars until all in t are covered
- Shrink left to minimize window while keeping all chars
- Track char frequencies and valid count
- Return smallest window found or empty if none

Full Transcript

The Minimum Window Substring problem finds the smallest substring in s containing all characters of t. We use a sliding window with two pointers, left and right. We expand right to include characters and update a frequency map to track needed chars. When the window contains all required chars (valid_count equals target length), we try to shrink from left to find a smaller valid window. We update the minimum window substring whenever a smaller valid window is found. This process continues until right reaches the end of s. The final result is the smallest substring containing all chars of t or empty if none exists.

Practice

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

easy

A. Reverse the entire string

B. Sort a string in ascending order

C. Count the number of vowels in a string

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 part of a string that includes all characters from another string.

2. Step 2: Identify the goal

   We want the minimum length substring that contains all required characters, not sorting or counting.

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 containing all chars [OK]

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

Common Mistakes:

• Confusing with sorting or reversing strings
• Thinking it counts characters instead of finding substring
• Ignoring the requirement to include all characters

2. Which Rust data structure is most suitable to track character counts when solving Minimum Window Substring?

easy

A. Vec<char>

B. HashMap

C. LinkedList<char>

D. BinaryHeap<char>

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 current window.

2. Step 2: Choose a data structure that maps characters to counts

   A HashMap allows storing counts for each character efficiently.

3. Final Answer:

   HashMap -> Option B

4. Quick Check:

   Use HashMap for char counts [OK]

Hint: Use HashMap to map chars to counts [OK]

Common Mistakes:

• Using Vec<char> which doesn't track counts
• Choosing LinkedList which is inefficient here
• Using BinaryHeap which is for priority, not counts

3. What is the output of the following Rust code snippet for Minimum Window Substring?

let s = "ADOBECODEBANC";
let t = "ABC";
let result = min_window(s, t);
println!("{}", result);

fn min_window(s: &str, t: &str) -> String {
    use std::collections::HashMap;
    let mut need = HashMap::new();
    for c in t.chars() {
        *need.entry(c).or_insert(0) += 1;
    }
    let (mut left, mut right, mut count) = (0, 0, 0);
    let mut min_len = usize::MAX;
    let mut start = 0;
    let mut window = HashMap::new();
    let s_chars: Vec<char> = s.chars().collect();
    while right < s_chars.len() {
        let c = s_chars[right];
        if need.contains_key(&c) {
            *window.entry(c).or_insert(0) += 1;
            if window[&c] == need[&c] {
                count += 1;
            }
        }
        while count == need.len() {
            if right - left + 1 < min_len {
                min_len = right - left + 1;
                start = left;
            }
            let left_char = s_chars[left];
            if need.contains_key(&left_char) {
                *window.entry(left_char).or_insert(0) -= 1;
                if window[&left_char] < need[&left_char] {
                    count -= 1;
                }
            }
            left += 1;
        }
        right += 1;
    }
    if min_len == usize::MAX {
        "".to_string()
    } else {
        s_chars[start..start + min_len].iter().collect()
    }
}

medium

A. "BANC"

B. "ADOBEC"

C. "CODEBA"

D. "ABC"

Solution

1. Step 1: Understand the input strings

   We want the smallest substring of "ADOBECODEBANC" containing all chars of "ABC".

2. Step 2: Trace the sliding window algorithm

   The code finds "BANC" as the minimum window containing 'A', 'B', and 'C'.

3. Final Answer:

   "BANC" -> Option A

4. Quick Check:

   Minimum window substring = "BANC" [OK]

Hint: Trace sliding window to find smallest valid substring [OK]

Common Mistakes:

• Choosing first found substring instead of minimum
• Ignoring character counts in window
• Confusing substring boundaries

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

fn min_window(s: &str, t: &str) -> String {
    use std::collections::HashMap;
    let mut need = HashMap::new();
    for c in t.chars() {
        *need.entry(c).or_insert(0) += 1;
    }
    let (mut left, mut right, mut count) = (0, 0, 0);
    let mut min_len = usize::MAX;
    let mut start = 0;
    let mut window = HashMap::new();
    let s_chars: Vec<char> = s.chars().collect();
    while right <= s_chars.len() {
        let c = s_chars[right];
        if need.contains_key(&c) {
            *window.entry(c).or_insert(0) += 1;
            if window[&c] == need[&c] {
                count += 1;
            }
        }
        while count == need.len() {
            if right - left + 1 < min_len {
                min_len = right - left + 1;
                start = left;
            }
            let left_char = s_chars[left];
            if need.contains_key(&left_char) {
                *window.entry(left_char).or_insert(0) -= 1;
                if window[&left_char] < need[&left_char] {
                    count -= 1;
                }
            }
            left += 1;
        }
        right += 1;
    }
    if min_len == usize::MAX {
        "".to_string()
    } else {
        s_chars[start..start + min_len].iter().collect()
    }
}

medium

A. The function returns a &str instead of String

B. The count variable is never incremented

C. The loop condition should be right < s_chars.len() instead of <= to avoid out-of-bounds

D. The window HashMap is not initialized

Solution

1. Step 1: Check the while loop boundary

   The loop uses right <= s_chars.len(), which causes out-of-bounds access at s_chars[right].

2. Step 2: Correct the loop condition

   Changing it to right < s_chars.len() prevents accessing beyond the vector length.

3. Final Answer:

   The loop condition should be right < s_chars.len() instead of <= to avoid out-of-bounds -> Option C

4. Quick Check:

   Loop boundary must prevent out-of-bounds [OK]

Hint: Check loop limits to avoid indexing errors [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Ignoring vector length causing panic
• Not incrementing count correctly

5. Given the strings s = "aabbccdd" and t = "abc", what is the minimum window substring that contains all characters of t? Consider the Rust sliding window approach.

hard

A. "aabbc"

B. "abc"

C. "abbc"

D. "bcca"

Solution

1. Step 1: Identify required characters and counts

   String t requires 'a', 'b', and 'c' once each.

2. Step 2: Find smallest substring in s containing all

   "aabbc" (positions 0 to 4) contains 'a', 'a', 'b', 'b', 'c' and is the smallest window covering all required chars.

3. Final Answer:

   "aabbc" -> Option A

4. Quick Check:

   Minimum window substring = "aabbc" [OK]

Hint: Slide window to cover all chars, then shrink to minimum [OK]

Common Mistakes:

• Choosing substring missing one required character
• Picking longer substring than necessary
• Ignoring character counts in window