LeetCode 76: Minimum Window Substring – Optimal C++ Solution Using Sliding Window
Minimum Window Substring in C++
LeetCode 76 · Sliding Window · Frequency Counting · Two Pointers
Table of Contents
- Problem Statement
- Approach
- Algorithm
- C++ Program
- Input
- Sample Output
- Output
- Explanation
- Dry Run
- Flow of Execution
- Time Complexity
- Space Complexity
- Applications
- Key Points
- Interview Questions
- Frequently Asked Questions
- Conclusion
Problem Statement
Given two strings s and t, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If no such substring exists, return an empty string.
Approach
This solution uses the Sliding Window technique with two pointers, start and end, and a frequency array.
The map array stores the required frequency of each character in string t. The variable count tracks how many characters are still required to form a valid window.
The end pointer expands the window by including characters from string s. Whenever a required character is found, its frequency is updated and count is decreased.
When count == 0, the current window contains all required characters. We try to shrink the window from the left to find a smaller valid substring.
Whenever a smaller valid window is found, its starting position and length are stored in startIndex and minLen.
Algorithm
- Check whether either string is empty or whether
sis shorter thant. - Create a frequency array of size 128 initialized with zeros.
- Initialize
countwith the length of stringt. - Store the frequency of every character in
t. - Initialize
start,end,minLenandstartIndex. - Expand the window using the
endpointer. - Decrease
countwhen a required character is included. - When
count == 0, a valid window is found. - Update the minimum window length if the current window is smaller.
- Shrink the window using the
startpointer. - If a required character is removed, increase
count. - Return the minimum window substring or an empty string.
C++ Program
Input
s = "ADOBECODEBANC" t = "ABC"
The required characters are A, B and C. We need to find the smallest substring of s that contains all three characters.
Sample Output
"BANC"
Output
The function returns the smallest substring containing all characters of t.
s = "ADOBECODEBANC", t = "ABC" → "BANC" s = "a", t = "a" → "a" s = "a", t = "aa" → ""
Explanation
Step 1: Handle edge cases
if (s.empty() || t.empty() || s.length() < t.length()) {
return "";
}If either string is empty, or the source string is shorter than the target string, a valid window cannot exist. Therefore, return an empty string.
Step 2: Initialize the frequency array
std::vector<int> map(128, 0); int count = t.length();
The frequency array stores the required frequency of ASCII characters. The count variable initially stores the total number of characters required from string t.
Step 3: Initialize pointers and variables
int start = 0, end = 0, minLen = INT_MAX, startIndex = 0;
start represents the beginning of the current window. end represents its ending position. minLen stores the smallest valid window length, and startIndex stores its starting position.
Step 4: Store the frequency of characters
for (char c : t) {
map[c]++;
}Every character in string t increments its corresponding frequency in the array.
For example, if t = "ABC", the required frequencies of A, B and C are each 1.
Step 5: Expand the window
while (end < s.length()) {
if (map[s[end++]]-- > 0) {
count--;
}
}The end pointer expands the window by including one character at a time.
If the character is still required, its frequency is positive before decrementing, so count decreases.
If the character is not required or its required frequency is already satisfied, count does not decrease.
Step 6: Check whether the window is valid
while (count == 0) {When count == 0, all required characters have been included in the current window. We can now try to reduce its size.
Step 7: Update the minimum window
if (end - start < minLen) {
startIndex = start;
minLen = end - start;
}If the current valid window is smaller than the previously stored window, update its starting index and minimum length.
Step 8: Shrink the window
if (map[s[start++]]++ == 0) {
count++;
}Remove the character at the left side of the window and increase its frequency in the array.
If its previous frequency was zero, that character was exactly satisfied before removal. Removing it means the window is no longer valid, so count increases.
Step 9: Return the minimum window
return minLen == INT_MAX ? "" : s.substr(startIndex, minLen);
If no valid window was found, return an empty string. Otherwise, return the substring using the stored starting position and minimum length.
Dry Run
Input: s = "ADOBECODEBANC", t = "ABC"
Initially, count = 3, because we need A, B and C.
| Window | Action | Count |
|---|---|---|
| A | A found | 2 |
| AD | D not required | 2 |
| ADO | O not required | 2 |
| ADOB | B found | 1 |
| ADOBE | E not required | 1 |
| ADOBEC | C found | 0 |
| ADOBEC | Valid window; save length 6 | 0 |
| DOBEC | A removed; window invalid | 1 |
| CODEBANC | Continue expanding | 1 |
| CODEBANC | A found | 0 |
| ODEBANC | Remove C; window invalid | 1 |
Final shrinking process
When the window reaches "BANC", all required characters are present.
B A N C | | start end
The window length is 4. Removing B would make the window invalid, so the algorithm stops shrinking this valid window.
The minimum window is "BANC".
Final result: "BANC"
Flow of Execution
Start
|
v
Read strings s and t
|
v
Check edge cases
|
v
Initialize frequency array
|
v
Store frequencies of t
|
v
Expand window using end
|
v
Is character required?
| Yes | No
v v
Decrease count Continue
|
v
Is count == 0?
| No | Yes
v v
Expand window Update minimum window
|
v
Shrink from left
|
v
Did a required character
become missing?
| Yes | No
v v
Increase Continue
count shrinking
|
v
Expand window
|
v
More characters?
| Yes | No
v v
Continue Return result
Time Complexity
| Operation | Complexity |
|---|---|
| Initialize frequency array | O(128) = O(1) |
| Build frequency map | O(|t|) |
| Expand window | O(|s|) |
| Shrink window | O(|s|) |
| Return substring | O(k) |
| Overall | O(|s| + |t|) |
The end pointer moves through string s at most once. Similarly, the start pointer also moves forward at most once through the string.
Building the frequency array takes O(|t|) time. Therefore, the overall time complexity is O(|s| + |t|), including the returned substring operation.
Space Complexity
The frequency array contains exactly 128 integer elements. Its size remains constant regardless of the input string length.
Therefore, the auxiliary space complexity is O(1).
The returned substring requires O(k) additional space, where k is the length of the resulting substring.
Applications
- Finding minimum substring windows.
- Character frequency counting.
- Text searching and processing.
- Pattern matching problems.
- Learning the sliding window technique.
- Preparing for string-based coding interviews.
Key Points
- The algorithm uses the sliding window technique.
startandendare the two pointers.- The frequency array stores the required character counts.
counttracks the number of required characters still missing.- The
endpointer expands the window. - The
startpointer shrinks the window. count == 0indicates that the current window is valid.minLenstores the minimum window length.startIndexstores the starting index of the minimum window.- The algorithm handles duplicate characters in string
t. - Time complexity is O(|s| + |t|).
- Auxiliary space complexity is O(1).
Interview Questions
- What is the Minimum Window Substring problem?
- Why is the sliding window technique suitable?
- Why do we use two pointers?
- What does the frequency array store?
- What is the purpose of the
countvariable? - Why do we initially set count to the length of string t?
- Why does the end pointer move forward?
- Why does the start pointer move forward?
- What does
count == 0indicate? - Why do we update
minLen? - What is the purpose of
startIndex? - Why do we increase the frequency when shrinking the window?
- How does the algorithm handle duplicate characters?
- What is the time complexity?
- What is the space complexity?
Frequently Asked Questions
1. What does the Minimum Window Substring problem ask?
It asks us to find the smallest substring of s that contains every character of t, including duplicate characters.
2. Which algorithm is used?
The solution uses the Sliding Window technique with two pointers and a frequency array.
3. What does count represent?
It represents the total number of required characters that are still missing from the current window.
4. When does a window become valid?
When count == 0, all required characters are included in the current window.
5. Why do we shrink the window?
We shrink the window to remove unnecessary characters and find the smallest valid substring.
6. How are duplicate characters handled?
The frequency array stores how many times each character is required, so duplicate characters are handled correctly.
7. What happens if no valid window exists?
The function returns an empty string.
8. What is the time complexity?
The overall time complexity is O(|s| + |t|).
9. What is the space complexity?
The auxiliary space complexity is O(1), because the frequency array has a fixed size of 128.
Conclusion
LeetCode 76 – Minimum Window Substring can be solved efficiently using the Sliding Window technique, two pointers and a frequency array.
The algorithm expands the window to include all required characters and shrinks it whenever a valid window is found. By continuously updating the minimum window length, we obtain the smallest substring containing all characters of the target string.
The overall time complexity is O(|s| + |t|), and the auxiliary space complexity is O(1).
Search Description
LeetCode 76 Minimum Window Substring C++ solution using sliding window, two pointers and frequency array. Learn the algorithm, dry run, flow of execution, time complexity, space complexity, interview questions and FAQs.
Keywords
Minimum Window Substring, LeetCode 76 C++ solution, Sliding Window C++, Minimum Substring Problem, Two Pointer Algorithm, Frequency Array C++, DSA in C++, String Problems, Coding Interview Questions, LeetCode String Problems
Hashtags
#CppProgramming #Cpp #LeetCode #MinimumWindowSubstring #SlidingWindow #TwoPointers #StringProblems #DSA #CodingInterview #Algorithms #LearnCpp #1printf
Comments
Post a Comment