Minimum Window Substring in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Minimum Window Substring Function

What is the output of the following C++ code that finds the minimum window substring?

DSA C++

std::string minWindow(std::string s, std::string t) {
    std::unordered_map<char, int> dictT;
    for (char c : t) dictT[c]++;
    int required = dictT.size();
    int l = 0, r = 0, formed = 0;
    std::unordered_map<char, int> windowCounts;
    int minLen = INT_MAX, minLeft = 0;
    while (r < s.size()) {
        char c = s[r];
        windowCounts[c]++;
        if (dictT.count(c) && windowCounts[c] == dictT[c]) formed++;
        while (l <= r && formed == required) {
            c = s[l];
            if (r - l + 1 < minLen) {
                minLen = r - l + 1;
                minLeft = l;
            }
            windowCounts[c]--;
            if (dictT.count(c) && windowCounts[c] < dictT[c]) formed--;
            l++;
        }
        r++;
    }
    return minLen == INT_MAX ? "" : s.substr(minLeft, minLen);
}

int main() {
    std::string s = "ADOBECODEBANC";
    std::string t = "ABC";
    std::cout << minWindow(s, t) << std::endl;
    return 0;
}

A "ABC"

B "ADOBEC"

C "CODEBA"

D "BANC"

💡 Hint

Think about the smallest substring containing all characters of t.

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

🧠 Conceptual

intermediate

Understanding the Sliding Window Technique

In the minimum window substring problem, why do we move the left pointer forward when the current window contains all required characters?

A To reset the window and start over from the right pointer.

B To increase the window size and include more characters.

C To try to find a smaller valid window by removing unnecessary characters from the left.

D To skip characters that are not in the target string t.

💡 Hint

Think about minimizing the window size while keeping it valid.

Moving the left pointer forward helps shrink the window to the smallest size that still contains all required characters.

🔧 Debug

advanced

Identify the Bug in Window Count Update

What error will occur in this code snippet from the minimum window substring algorithm? std::unordered_map windowCounts; windowCounts[s[r]]++; if (dictT.count(s[r]) && windowCounts[s[r]] == dictT[s[r]]) formed++; // Later when moving left pointer windowCounts[s[l]]--; if (dictT.count(s[l]) && windowCounts[s[l]] < dictT[s[l]]) formed--; l++;

A windowCounts[s[r]]++ causes a runtime error if s[r] is not in dictT.

B formed variable may be decremented incorrectly if windowCounts[s[l]] becomes negative.

C No error; code works correctly.

D formed variable is never incremented because dictT.count(s[r]) always returns false.

💡 Hint

Consider what happens if windowCounts[s[l]] goes below zero.

If windowCounts[s[l]] is decremented below zero, formed may be decremented incorrectly, causing logic errors.

❓ Predict Output

advanced

Output of Minimum Window Substring with Repeated Characters

What is the output of this code snippet? std::string s = "aabbcc"; std::string t = "abc"; std::cout << minWindow(s, t) << std::endl;

DSA C++

std::string minWindow(std::string s, std::string t) {
    std::unordered_map<char, int> dictT;
    for (char c : t) dictT[c]++;
    int required = dictT.size();
    int l = 0, r = 0, formed = 0;
    std::unordered_map<char, int> windowCounts;
    int minLen = INT_MAX, minLeft = 0;
    while (r < s.size()) {
        char c = s[r];
        windowCounts[c]++;
        if (dictT.count(c) && windowCounts[c] == dictT[c]) formed++;
        while (l <= r && formed == required) {
            c = s[l];
            if (r - l + 1 < minLen) {
                minLen = r - l + 1;
                minLeft = l;
            }
            windowCounts[c]--;
            if (dictT.count(c) && windowCounts[c] < dictT[c]) formed--;
            l++;
        }
        r++;
    }
    return minLen == INT_MAX ? "" : s.substr(minLeft, minLen);
}

A "abbc"

B "abc"

C "aabbc"

D "abbcc"

💡 Hint

Look for the smallest substring containing at least one 'a', one 'b', and one 'c'.

The substring "abbc" is the smallest window containing all characters 'a', 'b', and 'c'.

🧠 Conceptual

expert

Time Complexity of Minimum Window Substring Algorithm

What is the time complexity of the standard sliding window algorithm for the minimum window substring problem, and why?

A O(n) because each character is visited at most twice by the two pointers.

B O(n log n) due to sorting the characters in the window.

C O(n^2) because the nested loops can scan the string multiple times.

D O(1) because the window size is fixed and small.

💡 Hint

Consider how many times the left and right pointers move over the string.

Each pointer moves forward at most n times, so total operations are proportional to 2n = O(n).

Practice

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

easy

A. Find the longest substring without repeating characters

B. Sort the characters of a string in ascending order

C. Count the number of substrings that contain a specific character

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 substring in a given string that contains all characters of another string, including duplicates.

2. Step 2: Compare with other substring problems

   Unlike longest substring or counting substrings, this problem focuses on minimum length substring covering all required characters.

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

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

Common Mistakes:

• Confusing with longest substring problems
• Ignoring duplicate characters in target string
• Thinking it's about sorting or counting substrings

2. Which of the following C++ STL containers is most suitable to keep track of character counts in the Minimum Window Substring problem?

easy

A. std::unordered_map

B. std::vector<int>

C. std::stack<char>

D. std::queue<int>

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 track them in the window.

2. Step 2: Choose container supporting key-value pairs with fast access

   std::unordered_map allows mapping characters to counts with average O(1) access, ideal for this purpose.

3. Final Answer:

   std::unordered_map<char, int> -> Option A

4. Quick Check:

   Use unordered_map for char counts [OK]

Hint: Use unordered_map for fast char count lookup [OK]

Common Mistakes:

• Using stack or queue which don't support key-value mapping
• Using vector without mapping char to index
• Using map which is slower than unordered_map

3. What will be the output of the following C++ code snippet for s = "ADOBECODEBANC" and t = "ABC"?

std::string minWindow(std::string s, std::string t) {
    std::unordered_map dictT;
    for (char c : t) dictT[c]++;
    int required = dictT.size();
    int l = 0, r = 0, formed = 0;
    std::unordered_map windowCounts;
    int minLen = INT_MAX, minLeft = 0;
    while (r < s.size()) {
        char c = s[r];
        windowCounts[c]++;
        if (dictT.count(c) && windowCounts[c] == dictT[c]) formed++;
        while (l <= r && formed == required) {
            if (r - l + 1 < minLen) {
                minLen = r - l + 1;
                minLeft = l;
            }
            windowCounts[s[l]]--;
            if (dictT.count(s[l]) && windowCounts[s[l]] < dictT[s[l]]) formed--;
            l++;
        }
        r++;
    }
    return minLen == INT_MAX ? "" : s.substr(minLeft, minLen);
}

std::cout << minWindow("ADOBECODEBANC", "ABC") << std::endl;

medium

A. ADOBEC

B. BANC

C. CODEBA

D. ABC

Solution

1. Step 1: Understand the sliding window approach

   The code expands the right pointer to include characters and contracts the left pointer to find the smallest window containing all chars of t.

2. Step 2: Trace the window updates for s="ADOBECODEBANC" and t="ABC"

   The smallest substring containing 'A', 'B', and 'C' is "BANC" starting at index 9 with length 4.

3. Final Answer:

   BANC -> Option B

4. Quick Check:

   Minimum window substring = BANC [OK]

Hint: Trace window expansion and contraction carefully [OK]

Common Mistakes:

• Choosing first found substring instead of minimum
• Ignoring character counts and duplicates
• Confusing substring indices

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

std::string minWindow(std::string s, std::string t) {
    std::unordered_map dictT;
    for (char c : t) dictT[c]++;
    int required = dictT.size();
    int l = 0, r = 0, formed = 0;
    std::unordered_map windowCounts;
    int minLen = INT_MAX, minLeft = 0;
    while (r < s.size()) {
        char c = s[r];
        windowCounts[c]++;
        if (dictT.count(c) && windowCounts[c] == dictT[c]) formed++;
        while (l <= r && formed == required) {
            if (r - l + 1 < minLen) {
                minLen = r - l + 1;
                minLeft = l;
            }
            windowCounts[s[l]]--;
            if (dictT.count(s[l]) && windowCounts[s[l]] < dictT[s[l]]) formed--;
            l++;
        }
        // Missing increment of r here
    }
    return minLen == INT_MAX ? "" : s.substr(minLeft, minLen);
}

medium

A. The right pointer 'r' is never incremented inside the loop

B. The function returns empty string always

C. The windowCounts map is not updated correctly

D. The variable 'formed' is never incremented

Solution

1. Step 1: Analyze the while loop controlling 'r'

   The loop uses 'r' to expand the window, but 'r' is never incremented inside the loop, causing an infinite loop.

2. Step 2: Identify missing increment

   Without 'r++' inside the loop, the window never expands, so the function cannot find the minimum window.

3. Final Answer:

   The right pointer 'r' is never incremented inside the loop -> Option A

4. Quick Check:

   Missing r++ causes infinite loop [OK]

Hint: Check loop variables increment carefully [OK]

Common Mistakes:

• Forgetting to increment pointers in loops
• Misusing condition checks for formed variable
• Not updating window counts correctly

5. Given strings s = "aabbccdd" and t = "abc", which of the following modifications to the standard Minimum Window Substring algorithm will correctly find the minimum window containing all characters of t even if t has duplicate characters like "aabc"?

hard

A. Use a set instead of a map to track characters

B. Ignore duplicates in t and only check unique characters

C. Use a frequency map for t and check counts exactly, including duplicates

D. Only check if all characters appear at least once, ignoring counts

Solution

1. Step 1: Understand the importance of duplicates in t

   If t contains duplicates, the algorithm must count how many times each character appears and ensure the window matches those counts.

2. Step 2: Modify frequency tracking to include exact counts

   Using a frequency map for t and comparing window counts exactly ensures duplicates are handled correctly.

3. Final Answer:

   Use a frequency map for t and check counts exactly, including duplicates -> Option C

4. Quick Check:

   Exact frequency counts handle duplicates [OK]

Hint: Count duplicates precisely using frequency maps [OK]

Common Mistakes:

• Ignoring duplicate characters in target string
• Using sets which lose count information
• Checking only presence, not frequency