Minimum Window Substring in DSA C++ - Build from Scratch

Minimum Window Substring

📖 Scenario: You are working on a text processing tool that needs to find the smallest part of a document containing all keywords.Imagine you have a long string and a set of characters you want to find inside it. Your task is to find the shortest substring that contains all those characters at least once.

🎯 Goal: Build a program that finds the minimum window substring in a given string that contains all characters of another string.

📋 What You'll Learn

Create a string variable s with the value "ADOBECODEBANC"

Create a string variable t with the value "ABC"

Create a function minWindow that takes two strings s and t and returns the minimum window substring of s containing all characters of t

Use sliding window technique with two pointers left and right

Print the result of minWindow(s, t)

💡 Why This Matters

🌍 Real World

Finding minimum window substrings is useful in search engines, text analysis, and bioinformatics where you need to locate specific patterns quickly.

💼 Career

Understanding sliding window techniques and hash maps is essential for software engineers working on string processing, data streaming, and performance-critical applications.

1

Create input strings

Create a string variable s with the value "ADOBECODEBANC" and a string variable t with the value "ABC".

DSA C++

// Create string s and string t with given values
// Your code here

Hint

Use string s = "ADOBECODEBANC"; and string t = "ABC"; to create the input strings.

2

Set up frequency map for characters in t

Create a unordered_map<char, int> called dictT and fill it with the frequency of each character in t.

DSA C++

#include 
#include 

using namespace std;

string s = "ADOBECODEBANC";
string t = "ABC";

#include 

// Create unordered_map dictT and count chars in t
// Your code here

Hint

Use a for loop to count each character in t and store counts in dictT.

3

Implement the minimum window substring function

Write a function string minWindow(string s, string t) that uses two pointers left and right to find the smallest substring of s containing all characters of t. Use unordered_map<char, int> to track counts and a variable formed to check when all required characters are included.

DSA C++

#include 
#include 
#include 

using namespace std;

string s = "ADOBECODEBANC";
string t = "ABC";

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

// Write minWindow function below
// Your code here

Hint

Use two pointers left and right to expand and contract the window. Track counts in windowCounts. Update formed when counts match. Update minimum length and start index when all required characters are included.

4

Print the minimum window substring

Print the result of calling minWindow(s, t).

DSA C++

#include 
#include 
#include 
#include 

using namespace std;

string s = "ADOBECODEBANC";
string t = "ABC";

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

string minWindow(string s, string t) {
    if (s.empty() || t.empty()) return "";

    unordered_map dictT;
    for (char c : t) dictT[c]++;

    unordered_map windowCounts;
    int required = dictT.size();
    int formed = 0;
    int left = 0, right = 0;
    int minLen = INT_MAX, minLeft = 0;

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

        if (dictT.count(c) && windowCounts[c] == dictT[c]) {
            formed++;
        }

        while (left <= right && formed == required) {
            c = s[left];

            if (right - left + 1 < minLen) {
                minLen = right - left + 1;
                minLeft = left;
            }

            windowCounts[c]--;
            if (dictT.count(c) && windowCounts[c] < dictT[c]) {
                formed--;
            }
            left++;
        }
        right++;
    }

    return minLen == INT_MAX ? "" : s.substr(minLeft, minLen);
}

// Print the minimum window substring
// Your code here

Hint

Call minWindow(s, t) and print the result using cout.

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