Minimum Window Substring

Problem Description

Given two strings s and t, return the minimum window substring of s that contains every character in t (including duplicates). If no such window exists, return "".

The answer is guaranteed to be unique.

Examples

Constraints

• m == s.length, n == t.length
• 1 ≤ m, n ≤ 10⁵
• s and t consist of uppercase and lowercase English letters.

Expand Until Valid, Then Contract Until Invalid, Record Each Valid State

The pattern: expand right until the window contains all of t. Then contract left as far as possible while it’s still valid, recording the window size each time. Repeat until right reaches the end.

The implementation detail that makes this fast: instead of checking all characters in the window each time, track a have counter (how many distinct characters currently meet their required frequency) against a required counter (total distinct characters needed). When have == required, the window is valid.

Solution 1: Brute Force

Check every substring of s and test whether it contains all characters of t.

import java.util.HashMap;
import java.util.Map;

class Solution {
    public String minWindow(String s, String t) {
        if (t.isEmpty()) return "";
        Map<Character, Integer> need = new HashMap<>();
        for (char c : t.toCharArray()) need.merge(c, 1, Integer::sum);

        String result = "";
        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 1; j <= s.length(); j++) {
                Map<Character, Integer> window = new HashMap<>();
                for (char c : s.substring(i, j).toCharArray()) window.merge(c, 1, Integer::sum);
                boolean valid = true;
                for (Map.Entry<Character, Integer> e : need.entrySet()) {
                    if (window.getOrDefault(e.getKey(), 0) < e.getValue()) { valid = false; break; }
                }
                if (valid && (result.isEmpty() || j - i < result.length())) {
                    result = s.substring(i, j);
                }
            }
        }
        return result;
    }
}

from collections import Counter

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        need = Counter(t)
        result = ""
        for i in range(len(s)):
            for j in range(i + 1, len(s) + 1):
                window = Counter(s[i:j])
                if all(window[c] >= need[c] for c in need):
                    if not result or j - i < len(result):
                        result = s[i:j]
        return result

#include <string>
#include <unordered_map>

class Solution {
public:
    std::string minWindow(std::string s, std::string t) {
        std::unordered_map<char, int> need;
        for (char c : t) need[c]++;
        std::string result = "";
        for (int i = 0; i < s.size(); i++) {
            std::unordered_map<char, int> window;
            for (int j = i; j < s.size(); j++) {
                window[s[j]]++;
                bool valid = true;
                for (auto& [c, cnt] : need) if (window[c] < cnt) { valid = false; break; }
                if (valid && (result.empty() || j - i + 1 < result.size()))
                    result = s.substr(i, j - i + 1);
            }
        }
        return result;
    }
};

Complexity Analysis:

• Time Complexity: O(m² * n). Two loops over s, plus frequency check against t.
• Space Complexity: O(m + n). Window and need maps.

Where it breaks: at m = n = 10⁵, completely unusable. The sliding window solution does this in O(m + n).

Solution 2: Sliding Window with have/need Counters

Maintain a frequency map need for t. Expand right, update the window map. When a character’s window count exactly meets its needed count, increment have. When have == required, the window is valid: record it, then contract left to find a smaller valid window.

import java.util.HashMap;
import java.util.Map;

class Solution {
    public String minWindow(String s, String t) {
        if (t.isEmpty()) return "";

        Map<Character, Integer> need = new HashMap<>();
        for (char c : t.toCharArray()) need.merge(c, 1, Integer::sum);

        int required = need.size();
        int have = 0;
        Map<Character, Integer> window = new HashMap<>();
        int left = 0, minLen = Integer.MAX_VALUE, resLeft = 0;

        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            window.merge(c, 1, Integer::sum);
            // check if this character's count just met the required amount
            if (need.containsKey(c) && window.get(c).equals(need.get(c))) have++;

            while (have == required) {
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    resLeft = left;
                }
                char lc = s.charAt(left);
                window.merge(lc, -1, Integer::sum);
                // check if removing left caused a required char to drop below needed
                if (need.containsKey(lc) && window.get(lc) < need.get(lc)) have--;
                left++;
            }
        }
        return minLen == Integer.MAX_VALUE ? "" : s.substring(resLeft, resLeft + minLen);
    }
}

from collections import Counter

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not t:
            return ""

        need = Counter(t)
        required = len(need)
        have = 0
        window = {}
        left = 0
        min_len = float('inf')
        res_left = 0

        for right in range(len(s)):
            c = s[right]
            window[c] = window.get(c, 0) + 1
            # check if this character's count just met the required amount
            if c in need and window[c] == need[c]:
                have += 1

            while have == required:
                if right - left + 1 < min_len:
                    min_len = right - left + 1
                    res_left = left
                lc = s[left]
                window[lc] -= 1
                # check if removing left caused a required char to drop below needed
                if lc in need and window[lc] < need[lc]:
                    have -= 1
                left += 1

        return s[res_left:res_left + min_len] if min_len != float('inf') else ""

#include <string>
#include <unordered_map>
#include <climits>

class Solution {
public:
    std::string minWindow(std::string s, std::string t) {
        if (t.empty()) return "";

        std::unordered_map<char, int> need, window;
        for (char c : t) need[c]++;

        int required = need.size(), have = 0;
        int left = 0, minLen = INT_MAX, resLeft = 0;

        for (int right = 0; right < s.size(); right++) {
            char c = s[right];
            window[c]++;
            // check if this character's count just met the required amount
            if (need.count(c) && window[c] == need[c]) have++;

            while (have == required) {
                if (right - left + 1 < minLen) { minLen = right - left + 1; resLeft = left; }
                char lc = s[left];
                window[lc]--;
                // check if removing left caused a required char to drop below needed
                if (need.count(lc) && window[lc] < need[lc]) have--;
                left++;
            }
        }
        return minLen == INT_MAX ? "" : s.substr(resLeft, minLen);
    }
};

Complexity Analysis:

• Time Complexity: O(m + n). Building need is O(n). Each character enters the window once (right pass) and leaves the window at most once (left pass).
• Space Complexity: O(m + n). The need and window maps together hold at most the distinct characters of both strings.

Where it breaks: the have counter only increments when the window count exactly equals the needed count, not when it exceeds it. This means have can never go above required, which is what makes the while termination condition safe.

Common Mistakes

• Incrementing have whenever a needed character is added, not only when the exact count is met. If t = "AA" and the window has 3 ‘A’s, have should only count ‘A’ once (when window count of ‘A’ first reached 2). Incrementing on every addition over-counts.
• Not decrementing have when left removes a character that drops below the needed count. This makes the algorithm think the window is still valid when it isn’t.
• Returning s[resLeft:resLeft + minLen] without checking minLen != MAX. If no valid window exists, this returns a garbage substring.

Frequently Asked Questions

Why use have and required counters instead of just checking all character counts each time? Checking all counts in need on every step is O(|t|) per step, which makes the total O(m * |t|). The have/required pattern reduces this check to O(1) by tracking the count of “satisfied” characters incrementally.

What if t contains characters not in s? The have counter never reaches required, the inner while loop never executes, and the function returns "". Correct.

How does this differ from “Longest Substring Without Repeating Characters”? Both use variable-size sliding windows with expand-right, contract-left mechanics. The validity condition is different: this problem requires all of t’s characters to be present; the other requires all characters in the window to be unique.

← All Problems