Minimum Window Substring in DSA Rust

Mental Model

Find the smallest part of a string that contains all characters of another string. We slide a window over the string, growing and shrinking it to find the minimum size that fits all needed characters.

Analogy: Imagine you have a long necklace with many beads and you want to find the shortest segment that contains all colors of beads you need. You move your fingers along the necklace, stretching and shrinking the segment until you find the smallest one with all colors.

S: A B C D E F G H I J K L M N O P
T: C F H
Window: [↑       ↓]
The window moves over S to cover all chars in T.

Dry Run Walkthrough

Input: S = "ADOBECODEBANC", T = "ABC"

Goal: Find the smallest substring in S that contains all characters A, B, and C

Step 1: Expand right pointer to include characters until window contains A, B, C

Window covers "ADOBEC" -> A -> D -> O -> B -> E -> C
Window: [A D O B E C]
Contains all chars A, B, C

Why: We need to find a window that has all required chars first

Step 2: Shrink left pointer to remove unnecessary chars while still containing A, B, C

Window shrinks to "DOBEC" -> D -> O -> B -> E -> C
Window: [D O B E C]
Still contains A? No, lost A

Why: Try to reduce window size but lost A, so stop shrinking

Step 3: Expand right pointer to include more chars to regain missing A

Window expands to "DOBECODEBA" -> D -> O -> B -> E -> C -> O -> D -> E -> B -> A
Window: [D O B E C O D E B A]
Contains A, B, C again

Why: We need to regain all chars after losing A

Step 4: Shrink left pointer to minimize window while keeping all chars

Window shrinks to "BANC" -> B -> A -> N -> C
Window: [B A N C]
Contains all chars A, B, C

Why: Try to find smaller window with all chars

Result:

Minimum window substring is "BANC"

Annotated Code

DSA Rust

use std::collections::HashMap;

fn min_window(s: String, t: String) -> String {
    let mut need = HashMap::new();
    for c in t.chars() {
        *need.entry(c).or_insert(0) += 1;
    }
    let mut window = HashMap::new();
    let (mut left, mut right) = (0, 0);
    let (mut valid, mut start, mut length) = (0, 0, usize::MAX);
    let s_chars: Vec<char> = s.chars().collect();

    while right < s_chars.len() {
        let c = s_chars[right];
        right += 1;
        if need.contains_key(&c) {
            *window.entry(c).or_insert(0) += 1;
            if *window.get(&c).unwrap() == *need.get(&c).unwrap() {
                valid += 1;
            }
        }

        while valid == need.len() {
            if right - left < length {
                start = left;
                length = right - left;
            }
            let d = s_chars[left];
            left += 1;
            if need.contains_key(&d) {
                if *window.get(&d).unwrap() == *need.get(&d).unwrap() {
                    valid -= 1;
                }
                *window.get_mut(&d).unwrap() -= 1;
            }
        }
    }

    if length == usize::MAX {
        "".to_string()
    } else {
        s_chars[start..start + length].iter().collect()
    }
}

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

for c in t.chars() { *need.entry(c).or_insert(0) += 1; }

Count required characters from T

while right < s_chars.len() { let c = s_chars[right]; right += 1;

Expand right pointer to include new character

if need.contains_key(&c) { *window.entry(c).or_insert(0) += 1; if *window[&c] == *need[&c] { valid += 1; } }

Update window counts and valid count if character requirement met

while valid == need.len() {

Shrink window from left while all required chars are included

if right - left < length { start = left; length = right - left; }

Update minimum window size and start position

let d = s_chars[left]; left += 1; if need.contains_key(&d) { if *window[&d] == *need[&d] { valid -= 1; } *window.get_mut(&d).unwrap() -= 1; }

Remove left character from window and update valid count

Output

BANC

Complexity Analysis

Time: O(n) because each character in S is visited at most twice by left and right pointers

Space: O(m) where m is the number of unique characters in T for the hash maps

vs Alternative: Naive approach checks all substrings, O(n^2), sliding window reduces to O(n)

Edge Cases

Empty string S or T

Returns empty string because no window can contain all chars

DSA Rust

if length == usize::MAX { "".to_string() }

T contains characters not in S

No valid window found, returns empty string

DSA Rust

if length == usize::MAX { "".to_string() }

S and T are the same string

Returns S itself as minimum window

DSA Rust

updates start and length when valid == need.len()

When to Use This Pattern

When asked to find the smallest substring containing all characters of another string, use the sliding window pattern with two pointers expanding and shrinking the window.

Common Mistakes

Mistake: Not shrinking the window from the left after finding a valid window
Fix: Add a loop to shrink the window while it still contains all required characters

Mistake: Not updating the minimum window size and start position correctly
Fix: Update minimum length and start index inside the shrinking loop when a smaller valid window is found

Summary

Finds the smallest substring in S containing all characters of T.

Use when you need to find a minimal segment covering all required elements.

Slide a window expanding right to include chars and shrinking left to minimize size while keeping all required chars.

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