Minimum Window Substring in DSA C++ - Time & Space Complexity

Time Complexity: Minimum Window Substring

O(n + m)

Understanding Time Complexity

We want to understand how the time needed to find the smallest substring containing all characters of another string changes as the input grows.

How does the running time grow when the input strings get longer?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

string minWindow(string s, string t) {
    unordered_map<char, int> need, window;
    for (char c : t) need[c]++;
    int left = 0, right = 0, valid = 0;
    int start = 0, len = INT_MAX;
    while (right < s.size()) {
        char c = s[right++];
        if (need.count(c)) {
            window[c]++;
            if (window[c] == need[c]) valid++;
        }
        while (valid == need.size()) {
            if (right - left < len) {
                start = left;
                len = right - left;
            }
            char d = s[left++];
            if (need.count(d)) {
                if (window[d] == need[d]) valid--;
                window[d]--;
            }
        }
    }
    return len == INT_MAX ? "" : s.substr(start, len);
}
    

This code finds the smallest substring in s that contains all characters of t.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that moves right pointer through string s, and the inner while loop that moves left pointer to shrink the window.
• How many times: Each character in s is visited at most twice: once when right moves forward, once when left moves forward.

How Execution Grows With Input

As the input string s grows, the pointers move through it mostly once each, so the operations grow roughly in proportion to the length of s.

Input Size (n = length of s)	Approx. Operations
10	About 20 moves of pointers
100	About 200 moves of pointers
1000	About 2000 moves of pointers

Pattern observation: The number of operations grows roughly linearly with input size.

Final Time Complexity

Time Complexity: O(n + m)

This means the time grows linearly with the size of both input strings s and t.

Common Mistake

[X] Wrong: "Because there are nested loops, the time must be quadratic O(n²)."

[OK] Correct: The inner loop moves the left pointer forward only when the outer loop moves right, so each pointer moves at most n times, making it linear, not quadratic.

Interview Connect

Understanding this sliding window approach and its linear time complexity shows you can handle efficient substring problems, a common skill interviewers look for.

Self-Check

"What if we replaced the unordered_map with a fixed-size array for characters? How would the time complexity change?"

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