Skip to main content
CodePeetCodePeet
CodePeet 250

Minimum Window Substring

HARDProblemSolveExternal Links

Description

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 "".

A window substring is a contiguous sequence of characters within s. The window must contain every character that appears in t with at least the same frequency. For example, if t = "AAB", then the window must contain at least two As and one B.

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

Examples

Example 1

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

Output: "BANC"

Explanation: The minimum window substring "BANC" (from index 9 to 12) contains 'A', 'B', and 'C' from string t. No shorter substring of s contains all three characters.

Example 2

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

Output: "a"

Explanation: The entire string s is the minimum window, and it contains the single character from t.

Example 3

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

Output: ""

Explanation: Both 'a's from t must be included in the window. Since s only has one 'a', it is impossible to form a valid window. Return empty string.

Constraints

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

Editorial

Brute Force

Intuition

The most straightforward approach is to check every possible substring of s and see if it contains all the characters of t with the required frequencies.

For each starting index i and ending index j in s, extract the substring s[i..j], count its character frequencies, and verify that every character in t appears at least as many times. Among all valid substrings, return the shortest one.

This is the brute force definition of the problem — enumerate all candidates and pick the best. It is extremely slow for large inputs because there are O(n²) possible substrings, and checking each one takes O(n) time in the worst case.

Algorithm

  1. Count the frequency of each character in t → store in need map
  2. For each starting position i from 0 to m-1:
    • For each ending position j from i to m-1:
      • Count the frequency of characters in s[i..j]
      • Check if every character in need is present with sufficient frequency
      • If valid and shorter than the current best, update the result
  3. Return the shortest valid substring, or "" if none found

Code

class Solution {
public:
    string minWindow(string s, string t) {
        int m = s.size();
        unordered_map<char, int> need;
        for (char c : t) need[c]++;
        
        string result = "";
        int minLen = INT_MAX;
        
        for (int i = 0; i < m; i++) {
            unordered_map<char, int> windowCount;
            for (int j = i; j < m; j++) {
                windowCount[s[j]]++;
                
                // Check if current window contains all chars of t
                bool valid = true;
                for (auto& [ch, cnt] : need) {
                    if (windowCount[ch] < cnt) {
                        valid = false;
                        break;
                    }
                }
                
                if (valid && (j - i + 1) < minLen) {
                    minLen = j - i + 1;
                    result = s.substr(i, minLen);
                }
            }
        }
        return result;
    }
};
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        from collections import Counter
        m = len(s)
        need = Counter(t)
        result = ""
        min_len = float('inf')
        
        for i in range(m):
            window_count = Counter()
            for j in range(i, m):
                window_count[s[j]] += 1
                
                # Check if current window contains all chars of t
                valid = all(window_count[ch] >= cnt for ch, cnt in need.items())
                
                if valid and (j - i + 1) < min_len:
                    min_len = j - i + 1
                    result = s[i:j + 1]
        
        return result
class Solution {
    public String minWindow(String s, String t) {
        int m = s.length();
        Map<Character, Integer> need = new HashMap<>();
        for (char c : t.toCharArray()) need.merge(c, 1, Integer::sum);
        
        String result = "";
        int minLen = Integer.MAX_VALUE;
        
        for (int i = 0; i < m; i++) {
            Map<Character, Integer> windowCount = new HashMap<>();
            for (int j = i; j < m; j++) {
                windowCount.merge(s.charAt(j), 1, Integer::sum);
                
                // Check if current window contains all chars of t
                boolean valid = true;
                for (var entry : need.entrySet()) {
                    if (windowCount.getOrDefault(entry.getKey(), 0) < entry.getValue()) {
                        valid = false;
                        break;
                    }
                }
                
                if (valid && (j - i + 1) < minLen) {
                    minLen = j - i + 1;
                    result = s.substring(i, j + 1);
                }
            }
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(m² × |Σ|)

We have O(m²) possible substrings. For each substring, we incrementally update the frequency count in O(1), then verify validity by iterating over the need map which has at most |Σ| entries (where |Σ| is the alphabet size, at most 52 for English letters). So total is O(m² × |Σ|). A naive implementation that re-scans each substring character-by-character would be O(m³).

Space Complexity: O(|Σ|)

We store two frequency maps, each with at most |Σ| entries.

Why This Approach Is Not Efficient

The brute force generates O(m²) substrings and checks each one. With m up to 10⁵, this means up to 10¹⁰ operations — far too slow to pass within typical time limits.

The core waste is redundant work: when we shift the starting index from i to i+1, we throw away all the counting work we did for the window starting at i. We also do not exploit a key structural insight: once a window [i..j] is valid (contains all characters of t), extending it further to [i..j+1] is still valid — so there is no point exploring longer windows from the same start.

The sliding window technique addresses both issues. Instead of two nested loops that independently pick start and end, we maintain a single expanding/contracting window. The right pointer expands until we find a valid window, then the left pointer contracts to minimize it. Each pointer moves at most m times total, giving O(m) amortized traversal instead of O(m²).

Optimal Approach - Sliding Window

Intuition

The sliding window technique is the classic approach for this problem. The idea is to maintain two pointers, left and right, that define a window in string s. We expand the window by moving right forward until the window contains all characters of t. Once valid, we contract the window by moving left forward to find the smallest valid window from this position.

To efficiently track whether our window is valid, we use:

  • A need map storing the required frequency of each character in t
  • A window map storing the current frequency of each character in our window
  • A matched counter that tracks how many individual character slots from t are satisfied

The matched counter is the key optimization. Instead of comparing the entire frequency maps every time a character enters or leaves the window (which would cost O(|Σ|) per step), we maintain matched incrementally:

  • When a character enters the window and its count goes from below the required frequency to meeting it → increment matched
  • When a character leaves the window and its count drops below the required frequency → decrement matched

When matched == len(t), the window is valid. This gives us O(1) validity checking.

Think of it like filling a shopping list. You walk through a grocery store (moving right), picking up items until you have everything on the list. Then you start putting back items from the earliest picks (moving left) to see how few items you actually need in your cart while still having everything required.

Step-by-Step Explanation

Let's trace through s = "ADOBECODEBANC", t = "ABC":

Setup:

  • need = {A:1, B:1, C:1}, required = 3 total character slots
  • window = {}, matched = 0, left = 0, result = ""

Phase 1: Expand to first valid window

  • right=0, char='A': window={A:1}. A's count reached need → matched=1
  • right=1, char='D': window={A:1,D:1}. D not in need → matched=1
  • right=2, char='O': window={A:1,D:1,O:1}. O not in need → matched=1
  • right=3, char='B': window={A:1,D:1,O:1,B:1}. B's count reached need → matched=2
  • right=4, char='E': window adds E → matched=2
  • right=5, char='C': window adds C. C's count reached need → matched=3 ✓

Valid window found: "ADOBEC" (0 to 5), length=6 → result="ADOBEC"

Phase 2: Contract from left

  • left=0, removing 'A': A's count drops below need → matched=2. Window invalid, stop contracting.
  • left is now 1.

Phase 3: Continue expanding

  • right=6 'O', right=7 'D', right=8 'E', right=9 'B': No new needed chars satisfied
  • right=10, char='A': A's count reaches need again → matched=3 ✓

Valid window: "DOBECODEBA" (1 to 10), length=10 — worse than 6, don't update.

Phase 4: Contract

  • left=1 remove 'D': not in need → matched=3, still valid. Window (2,10), length=9
  • left=2 remove 'O': not in need → matched=3, still valid. Window (3,10), length=8
  • left=3 remove 'B': B count drops but still ≥ need (window has 2 B's, need 1) → matched=3, still valid. Window (4,10), length=7
  • left=4 remove 'E': not in need → matched=3, still valid. Window (5,10), length=6 → same as best, don't update
  • left=5 remove 'C': C count drops below need → matched=2. Stop contracting.
  • left is now 6.

Phase 5: Continue expanding

  • right=11, char='N': not in need → matched=2
  • right=12, char='C': C's count reaches need → matched=3 ✓

Valid window: "ODEBANC" (6 to 12), length=7 — worse than 6.

Phase 6: Contract

  • left=6 remove 'O': not in need → matched=3. Window (7,12), length=6
  • left=7 remove 'D': not in need → matched=3. Window (8,12), length=5
  • left=8 remove 'E': not in need → matched=3. Window (9,12), length=4 → NEW BEST! result="BANC"
  • left=9 remove 'B': B count drops below need → matched=2. Stop.

End of string. Return "BANC".

Sliding Window — Finding Minimum Window Substring — Watch how the window expands to capture all needed characters, then contracts to find the minimum valid substring, tracking character requirements with a matched counter.

Algorithm

  1. Count the frequency of each character in t → store in need map
  2. Initialize window map (empty), matched = 0, left = 0, result = "", minLen = ∞
  3. Expand by iterating right from 0 to m-1:
    a. Add s[right] to window map
    b. If s[right] is in need and window[s[right]] <= need[s[right]], increment matched
  4. While matched == len(t) (window is valid):
    a. If (right - left + 1) < minLen, update minLen and record the window start
    b. Remove s[left] from the window:
    • If s[left] is in need and window[s[left]] <= need[s[left]], decrement matched
    • Decrement window[s[left]]
    • Increment left
  5. Return the recorded minimum substring, or "" if none found

Code

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> need, window;
        for (char c : t) need[c]++;
        
        int left = 0, matched = 0;
        int minLen = INT_MAX, minStart = -1;
        
        for (int right = 0; right < (int)s.size(); right++) {
            char c = s[right];
            window[c]++;
            
            // If this character contributes to matching t
            if (need.count(c) && window[c] <= need[c]) {
                matched++;
            }
            
            // Contract window while it's valid
            while (matched == (int)t.size()) {
                // Update minimum window
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    minStart = left;
                }
                
                // Remove leftmost character
                char leftChar = s[left];
                if (need.count(leftChar) && window[leftChar] <= need[leftChar]) {
                    matched--;
                }
                window[leftChar]--;
                left++;
            }
        }
        
        return minStart == -1 ? "" : s.substr(minStart, minLen);
    }
};
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        from collections import Counter
        
        need = Counter(t)
        window = Counter()
        matched = 0
        left = 0
        min_len = float('inf')
        min_start = -1
        
        for right, char in enumerate(s):
            window[char] += 1
            
            # If this character contributes to matching t
            if char in need and window[char] <= need[char]:
                matched += 1
            
            # Contract window while it's valid
            while matched == len(t):
                # Update minimum window
                if right - left + 1 < min_len:
                    min_len = right - left + 1
                    min_start = left
                
                # Remove leftmost character
                left_char = s[left]
                if left_char in need and window[left_char] <= need[left_char]:
                    matched -= 1
                window[left_char] -= 1
                left += 1
        
        return "" if min_start == -1 else s[min_start:min_start + min_len]
class Solution {
    public String minWindow(String s, String t) {
        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();
        for (char c : t.toCharArray()) need.merge(c, 1, Integer::sum);
        
        int left = 0, matched = 0;
        int minLen = Integer.MAX_VALUE, minStart = -1;
        
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            window.merge(c, 1, Integer::sum);
            
            // If this character contributes to matching t
            if (need.containsKey(c) && window.get(c) <= need.get(c)) {
                matched++;
            }
            
            // Contract window while it's valid
            while (matched == t.length()) {
                // Update minimum window
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    minStart = left;
                }
                
                // Remove leftmost character
                char leftChar = s.charAt(left);
                if (need.containsKey(leftChar) && window.get(leftChar) <= need.get(leftChar)) {
                    matched--;
                }
                window.merge(leftChar, -1, Integer::sum);
                left++;
            }
        }
        
        return minStart == -1 ? "" : s.substring(minStart, minStart + minLen);
    }
}

Complexity Analysis

Time Complexity: O(m + n)

Building the need map from t takes O(n). The sliding window traversal processes string s with two pointers — right moves from 0 to m-1, and left only moves forward, never backward. Each pointer visits each character at most once, giving a total of at most 2m character visits. Combined: O(m + n). Each character operation (hash map insert/lookup) is O(1) amortized.

Space Complexity: O(|Σ|)

We store two frequency maps (need and window). Each map contains at most |Σ| entries, where |Σ| is the size of the character set. For uppercase and lowercase English letters, |Σ| = 52, making this effectively O(1) constant space. The output string is not counted as extra space.