LeetCode Solution 76 - Minimum Window Substring

Problem Statement

Given two strings s and t of lengths m and n, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return an empty string "".

The test cases will be generated such that the answer is unique.

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"

Example 2:

Input: s = "a", t = "a"
Output: "a"

Example 3:

Input: s = "a", t = "aa"
Output: ""

Optimal Approach - Sliding Window + HashMap

Explanation

We use a two-pointer technique (left and right pointers) to traverse the string while maintaining a character frequency map for t. The goal is to expand the window until all characters in t are found, then contract it to find the smallest valid window.

Steps:

1. Maintain a frequency map for t.
2. Use two pointers (left and right) to define a sliding window.
3. Expand the right pointer until we have all characters of t in the window.
4. Once all characters are included, move the left pointer to shrink the window while maintaining the condition.
5. Keep track of the minimum window found.

C++ Code Implementation

#include <unordered_map>
#include <climits>
using namespace std;

class Solution {
public:
    string minWindow(string s, string t) {
        if (s.empty() || t.empty()) return "";
        
        unordered_map<char, int> target, window;
        for (char c : t) target[c]++;
        
        int left = 0, right = 0, required = target.size(), formed = 0;
        int minLength = INT_MAX, startIndex = 0;
        
        while (right < s.size()) {
            char c = s[right];
            window[c]++;
            if (target.count(c) && window[c] == target[c]) {
                formed++;
            }
            
            while (formed == required) {
                if (right - left + 1 < minLength) {
                    minLength = right - left + 1;
                    startIndex = left;
                }
                
                char lc = s[left];
                window[lc]--;
                if (target.count(lc) && window[lc] < target[lc]) {
                    formed--;
                }
                left++;
            }
            right++;
        }
        
        return (minLength == INT_MAX) ? "" : s.substr(startIndex, minLength);
    }
};

Dry Run / Execution Steps

Input: s = "ADOBECODEBANC", t = "ABC"

1. Expand right until all characters in t are covered → "ADOBEC"
2. Contract left to shrink the window → "DOBEC"
3. Expand right again → "CODEBA"
4. Contract left → "ODEBA"
5. Continue until "BANC" is found as the shortest valid window.

Alternative Approaches & Why Not?

Approach	Time Complexity	Space Complexity	Reason for Not Choosing
Brute Force	O(m*n)	O(1)	Too slow, checks all substrings
Sorting	O(m log m)	O(m)	Sorting doesn’t preserve order
HashMap + Two Pointers	O(m)	O(m)	Best choice, efficient

Best Solution & Why It’s Best

The Sliding Window + HashMap approach is optimal because:

• It efficiently finds the minimum window substring in O(m) time.
• Uses only O(m) extra space for character tracking.
• Avoids unnecessary comparisons by dynamically shrinking the window.

Complexity Analysis

• Time Complexity: O(m) (Each character is processed at most twice)
• Space Complexity: O(m) (HashMap storage for t)

Conclusion

• The best approach is the Sliding Window + HashMap method.
• This technique is useful for similar problems like:
  • Longest Substring Without Repeating Characters
  • Find All Anagrams in a String

For more practice, check out related problems and internal links to solutions!