Minimum Window Substring in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Minimum Window Substring Function

What is the output of the following Rust function when called with s = "ADOBECODEBANC" and t = "ABC"?

DSA Rust

fn min_window(s: String, t: String) -> 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) = (0, 0);
    let (mut start, mut min_len) = (0, usize::MAX);
    let mut window = HashMap::new();
    let mut valid = 0;
    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[&c] == need[&c] {
                valid += 1;
            }
        }
        while valid == need.len() {
            if right - left < min_len {
                start = left;
                min_len = right - left;
            }
            let d = s_chars[left];
            left += 1;
            if need.contains_key(&d) {
                if window[&d] == need[&d] {
                    valid -= 1;
                }
                *window.entry(d).or_insert(0) -= 1;
            }
        }
    }
    if min_len == usize::MAX {
        "".to_string()
    } else {
        s_chars[start..start + min_len].iter().collect()
    }
}

A "DOBECODEBA"

B "BANC"

C "ADOBEC"

D "CODEBA"

💡 Hint

Think about the smallest substring that contains all characters of t.

The minimum window substring that contains all characters 'A', 'B', and 'C' in "ADOBECODEBANC" is "BANC".

🧠 Conceptual

intermediate

Understanding the Sliding Window Technique

In the context of the Minimum Window Substring problem, what is the main purpose of the sliding window technique?

A To sort the characters of the string before searching

B To find the longest substring without repeating characters

C To dynamically adjust the substring boundaries to find the smallest valid window containing all required characters

D To count the total number of substrings in the string

💡 Hint

Think about how the window changes size and position.

The sliding window technique moves the window boundaries to include or exclude characters, aiming to find the smallest substring that contains all characters of t.

🔧 Debug

advanced

Identify the Error in Rust Code for Minimum Window Substring

What error will occur when running this Rust code snippet for minimum window substring? let s = "a".to_string(); let t = "aa".to_string(); let result = min_window(s, t); println!("{}", result);

DSA Rust

fn min_window(s: String, t: String) -> 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) = (0, 0);
    let (mut start, mut min_len) = (0, usize::MAX);
    let mut window = HashMap::new();
    let mut valid = 0;
    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[&c] == need[&c] {
                valid += 1;
            }
        }
        while valid == need.len() {
            if right - left < min_len {
                start = left;
                min_len = right - left;
            }
            let d = s_chars[left];
            left += 1;
            if need.contains_key(&d) {
                if window[&d] == need[&d] {
                    valid -= 1;
                }
                *window.entry(d).or_insert(0) -= 1;
            }
        }
    }
    if min_len == usize::MAX {
        "".to_string()
    } else {
        s_chars[start..start + min_len].iter().collect()
    }
}

A The function returns an empty string because s does not contain enough characters to cover t

B The code panics due to index out of bounds when accessing s_chars

C The code causes a compile-time error due to mutable borrow conflicts

D The function returns the entire string s regardless of t

💡 Hint

Consider what happens when t has more occurrences of a character than s.

Since s = "a" and t = "aa", s does not have enough 'a's to cover t, so the function returns an empty string.

🚀 Application

advanced

Minimum Window Substring with Unicode Characters

Given the input strings s = "あいうえおかきくけこ" and t = "きえお", what is the minimum window substring returned by the function?

A "きかおえ"

B "きくけこ"

C "おかきくけ"

D "えおかき"

💡 Hint

Remember the function works with Unicode characters as well.

The smallest substring containing 'き', 'え', and 'お' is "えおかき".

🧠 Conceptual

expert

Time Complexity of Minimum Window Substring Algorithm

What is the time complexity of the sliding window algorithm used to solve the Minimum Window Substring problem?

A O(n), where n is the length of string s

B O(n^2), where n is the length of string s

C O(m * n), where m and n are lengths of strings s and t respectively

D O(log n), where n is the length of string s

💡 Hint

Consider how many times each pointer moves in the sliding window.

Each character in s is visited at most twice by the left and right pointers, resulting in O(n) time complexity.

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