Minimum Window Substring

Practice here

Given two strings s and t of lengths m and n respectively, 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 the empty string "".

The testcases will be generated such that the answer is unique.

Brute Force Approach#

Generate All substrings

1. Try every starting index i in s

   • Assume s[i...] might form a valid window.

2. Expand window with j

   • For every j ≥ i, check substring s[i..j].
   • Keep a copy of frequency map of t → tempMap.

3. Consume characters

   • For each s[j], decrement from tempMap.
   • If s[j] was needed (tempMap[s[j]] > 0 before decrement), reduce required.
   • required = how many chars are still missing to match t.

4. Check for valid window

   • When required == 0 → substring s[i..j] is valid.
   • Compare with current best (minLen) and update if smaller.
   • Break inner loop (since extending further only makes window larger).

5. Continue for next i

   • Repeat the above for all starting points.

class Solution {
public:
    string minWindow(string s, string t) {
        int n = s.size();
        int m = t.size();

        if(m==0 || n==0 || m > n){
            return "";
        }

        int startIdx = -1, minLen = INT_MAX;

        vector<int> freq(128);
        for(int j =0;j<m;j++){
            freq[t[j]]++;
        }

        for(int i=0;i<n;i++){
            vector<int> tempFreq= freq;
            int cnt = 0;

            for(int j=i;j<n;j++){
                if(tempFreq[s[j]] > 0){
                    cnt++;
                }

                tempFreq[s[j]]--;

                if(cnt == m){
                    if(minLen > j-i+1){
                        startIdx = i;
                        minLen = j-i+1;
                    } 
                    break;
                }
            }

        }
        return startIdx == -1 ? "" : s.substr(startIdx, minLen);
    }
};

Time Complexity: O(n²) --> TLE

Space Complexity: O(128) ~ O(1)

Better Solution: Sliding Window#

1. Build a frequency map for t
   • Suppose t = "ABC".
   • We need: { A:1, B:1, C:1 }.
   • This tells us which chars and how many we still need in the current window.
2. Expand the window (end pointer)
   • Start scanning s from left to right.
   • Each time you add s[end] into the window:
     • Decrease its need in the frequency map.
     • If that character was still required (need > 0), reduce required count.
   • Keep going until the window has all required characters → required == 0.
3. Contract the window (start pointer)
   • Now we’ve got a valid window. But it may not be the smallest.
   • Try moving start forward while keeping the window valid.
   • Each time before invalidating the window:
     • Update minLen if this new window is smaller.
   • As soon as the window becomes invalid (required > 0), stop contracting.
4. Repeat
   • Continue expanding end to search for new valid windows.
   • Always contract start as much as possible whenever you get a valid window.
   • Track the best (smallest) window seen.
5. Return the best window

• If no valid window found → return "".
• Otherwise → return substring [startIdx, startIdx+minLen).

• Expansion finds validity.
• Contraction finds minimality.

class Solution {
public:
    string minWindow(string s, string t) {
        int n = s.size();
        int m = t.size();

        if(m==0 || n==0 || m > n){
            return "";
        }

        int startIdx = -1, minLen = INT_MAX;

        vector<int> freq(128);
        for(int j = 0;j < m; j++){
            freq[t[j]]++;
        }

        int start = 0, cnt = 0;

        for(int end=0;end<n;end++){
            if(freq[s[end]] > 0){
                cnt++;
            }

            freq[s[end]]--;

            while(cnt == m){
                if(minLen > end-start+1){
                    startIdx = start;
                    minLen = end-start+1;
                } 
                freq[s[start]]++;
                if(freq[s[start]]>0)
                    cnt--;
                start++;
            }
        }
        return startIdx == -1 ? "" : s.substr(startIdx, minLen);
    }
};

Time Complexity: O(n)

Space Complexity: O(128) ~ O(1)

Follow-up#

If the character set was extremely large, how would that affect your choice between a hash map and a fixed-size array?

The current solution uses vector<int> freq(128) — a direct-indexed array over ASCII. That works great when the character domain is small and fixed, but breaks down as the domain grows:

Why the array wins for small sets:

• Index into the array is a single memory access — no hash computation, no collision handling.
• The whole array fits in L1/L2 cache, so repeated lookups are essentially free.

Why the map wins for large sets:

• An int[65536] array allocated on the heap wastes memory proportional to the domain size, not the actual number of distinct characters in t.
• unordered_map<int, int> (using Unicode code points as keys) uses memory proportional only to |t| — far cheaper when t is short but the alphabet is huge.
• The hash-map overhead (O(1) amortised but with a constant factor) becomes worth paying once the domain exceeds a few thousand characters.

Practical rule of thumb: if sizeof(domain) × sizeof(int) fits comfortably in cache (≲ 32 KB), use the array. Otherwise, prefer unordered_map and accept the hashing overhead.

Here is the sliding window rewritten with a vector<int>(256) — covers all extended ASCII without heap-allocated map nodes:

class Solution {
public:
    string minWindow(string s, string t) {
        int n = s.length();
        int m = t.length();

        vector<int> charFreqMap(256, 0);

        for (char c : t)
            charFreqMap[c]++;

        int startIdx = -1, minLen = INT_MAX, cnt = 0;
        int start = 0;

        for (int end = 0; end < n; end++) {
            if (charFreqMap[s[end]] > 0) // char was needed by t
                cnt++;

            charFreqMap[s[end]]--;

            while (cnt == m) { // all chars from t are in the window
                if (minLen > end - start + 1) {
                    startIdx = start;
                    minLen = end - start + 1;
                }

                charFreqMap[s[start]]++;
                if (charFreqMap[s[start]] > 0) // giving back a char t still needs
                    cnt--;
                start++;
            }
        }

        return startIdx == -1 ? "" : s.substr(startIdx, minLen);
    }
};

Time Complexity: O(n)

Space Complexity: O(256) ~ O(1)