Minimum Window Substring in DSA C++

Mental Model

Find the smallest part of a big string that contains all characters of a smaller string. We slide a window over the big string and adjust it to keep all needed characters.

Analogy: Imagine you have a big bookshelf and want to find the shortest section that contains all your favorite books. You move your hands along the shelf, expanding and shrinking the section until you find the smallest one with all favorites.

Big string:  A B C D E F G H I J K L M N O P
Window:      ↑             ↑
             start         end
Target chars: C, F, G

Dry Run Walkthrough

Input: big string: "ADOBECODEBANC", target string: "ABC"

Goal: Find the smallest substring in big string containing all characters A, B, and C

Step 1: Expand window end pointer to include characters until all target chars are covered

Window: A D O B E C (indices 0 to 5)
Contains A, B, C? Yes
Window substring: "ADOBEC"

Why: We need to include all target chars before trying to shrink

Step 2: Shrink window start pointer to remove unnecessary chars while still containing all target chars

Window: B E C (indices 3 to 5)
Contains A, B, C? No (missing A)
Window substring: "BEC"

Why: Removing A caused loss of target char, so stop shrinking

Step 3: Expand window end pointer to include more chars to regain missing target chars

Window: B E C O D E B A (indices 3 to 10)
Contains A, B, C? Yes
Window substring: "BECODEBA"

Why: We need to regain missing A to have all target chars

Step 4: Shrink window start pointer to minimize window while still containing all target chars

Window: B A N C (indices 9 to 12)
Contains A, B, C? Yes
Window substring: "BANC"

Why: Smaller window with all target chars found

Step 5: Try to shrink further but lose target chars, so stop

Window: A N C (indices 10 to 12)
Contains A, B, C? No (missing B)
Window substring: "ANC"

Why: Cannot remove B, so current smallest valid window is "BANC"

Result:

B A N C -> "BANC" is the smallest substring containing A, B, and C

Annotated Code

DSA C++

#include <iostream>
#include <string>
#include <unordered_map>
#include <climits>

using namespace std;

string minWindow(string s, string t) {
    unordered_map<char, int> target_count;
    for (char c : t) {
        target_count[c]++;
    }
    int required = target_count.size();
    int formed = 0;
    unordered_map<char, int> window_count;
    int left = 0, right = 0;
    int min_len = INT_MAX, min_left = 0;

    while (right < (int)s.size()) {
        char c = s[right];
        window_count[c]++;

        if (target_count.count(c) && window_count[c] == target_count[c]) {
            formed++;
        }

        while (left <= right && formed == required) {
            if (right - left + 1 < min_len) {
                min_len = right - left + 1;
                min_left = left;
            }
            char left_char = s[left];
            window_count[left_char]--;
            if (target_count.count(left_char) && window_count[left_char] < target_count[left_char]) {
                formed--;
            }
            left++;
        }
        right++;
    }

    return min_len == INT_MAX ? "" : s.substr(min_left, min_len);
}

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

for (char c : t) { target_count[c]++; }

Count each target character needed

window_count[c]++;

Add current character to window count

if (target_count.count(c) && window_count[c] == target_count[c]) { formed++; }

Increase formed count when a target char meets required frequency

while (left <= right && formed == required) {

Try to shrink window while all target chars are included

if (right - left + 1 < min_len) { min_len = right - left + 1; min_left = left; }

Update minimum window size and start index

window_count[left_char]--;

Remove left char from window count as window shrinks

if (target_count.count(left_char) && window_count[left_char] < target_count[left_char]) { formed--; }

Decrease formed count if window no longer satisfies target char frequency

left++;

Move left pointer to shrink window

right++;

Expand window by moving right pointer

Output

BANC

Complexity Analysis

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

Space: O(m) where m is size of target string due to frequency maps

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

Edge Cases

Empty big string or empty target string

Returns empty string immediately

DSA C++

return min_len == INT_MAX ? "" : s.substr(min_left, min_len);

Target string longer than big string

No valid window found, returns empty string

DSA C++

return min_len == INT_MAX ? "" : s.substr(min_left, min_len);

Target string with repeated characters

Window must contain required counts of repeated chars

DSA C++

if (target_count.count(c) && window_count[c] == target_count[c]) { formed++; }

When to Use This Pattern

When asked to find the smallest substring containing all characters of another string, use sliding window with frequency counts to efficiently find the minimum window.

Common Mistakes

Mistake: Not updating formed count correctly when shrinking window
Fix: Decrease formed only when window count falls below target count for a character

Mistake: Not checking if character is in target before updating formed
Fix: Check target_count.count(c) before comparing counts

Mistake: Not updating minimum window when a smaller valid window is found
Fix: Update min_len and min_left inside the shrinking loop when conditions are met

Summary

Finds the smallest substring in a big string containing all characters of a target string.

Use when you need to find a minimal window covering all required characters efficiently.

The key is to expand and shrink a sliding window while tracking character counts to maintain all required characters.

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