Minimum Window Substring in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the left pointer for the sliding window.

DSA C++

int left = [1];

Drag options to blanks, or click blank then click option'

A0

B1

C-1

Ds.size()

Attempts:

3 left

💡 Hint

Common Mistakes

Starting left at 1 skips the first character.

Using -1 causes invalid indexing.

The left pointer starts at index 0 to begin scanning the string from the start.

2fill in blank

medium

Complete the code to check if the current window contains all required characters.

DSA C++

if (formed == required) [1]

Drag options to blanks, or click blank then click option'

Acontinue;

Breturn true;

Cbreak;

DexpandRight();

Attempts:

3 left

💡 Hint

Common Mistakes

Using continue skips shrinking logic.

Returning true ends the function prematurely.

When the window contains all required characters, we can try to shrink it, so we break the current expansion loop.

3fill in blank

hard

Fix the error in updating the minimum window length.

DSA C++

if (end - start + 1 < minLen) {
    minLen = [1];
    minStart = start;
}

Drag options to blanks, or click blank then click option'

Aend - start + 1

Bstart - end + 1

Cend + start - 1

Dstart + end + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using start - end + 1 results in negative length.

Adding start and end incorrectly calculates length.

The window length is calculated as end - start + 1 because indices are zero-based and inclusive.

4fill in blank

hard

Fill both blanks to update the character count and move the left pointer.

DSA C++

windowCounts[s[start]] [1];
start [2];

Drag options to blanks, or click blank then click option'

A--

B++

C+=

D-=

Attempts:

3 left

💡 Hint

Common Mistakes

Incrementing the count instead of decrementing.

Moving start backward instead of forward.

We decrease the count of the character at start and then move start forward by incrementing it.

5fill in blank

hard

Fill both blanks to build the result substring from the original string.

DSA C++

return minLen == INT_MAX ? "" : s.[1](minStart, [2]);

Drag options to blanks, or click blank then click option'

Asubstr

BminLen

Clength

Dsize

Attempts:

3 left

💡 Hint

Common Mistakes

Using size or length as the second argument instead of minLen.

Using incorrect function name for substring.

Use substr to get the substring starting at minStart with length minLen.

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