Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

76. Minimum Window Substring - Leetcode Solution

Code Implementation

from collections import Counter

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not t or not s:
            return ""
        
        dict_t = Counter(t)
        required = len(dict_t)
        l, r = 0, 0
        formed = 0
        window_counts = {}
        ans = float("inf"), None, None
        
        while r < len(s):
            character = s[r]
            window_counts[character] = window_counts.get(character, 0) + 1

            if character in dict_t and window_counts[character] == dict_t[character]:
                formed += 1

            while l <= r and formed == required:
                character = s[l]
                if r - l + 1 < ans[0]:
                    ans = (r - l + 1, l, r)
                window_counts[character] -= 1
                if character in dict_t and window_counts[character] < dict_t[character]:
                    formed -= 1
                l += 1
            r += 1
        
        return "" if ans[0] == float("inf") else s[ans[1]:ans[2]+1]
      
#include <string>
#include <unordered_map>
#include <climits>
using namespace std;

class Solution {
public:
    string minWindow(string s, string t) {
        if (t.empty() || s.empty()) return "";
        unordered_map<char, int> dict_t;
        for (char c : t) dict_t[c]++;
        int required = dict_t.size();
        unordered_map<char, int> window_counts;
        int l = 0, r = 0, formed = 0;
        int min_len = INT_MAX, min_l = 0;
        
        while (r < s.size()) {
            char c = s[r];
            window_counts[c]++;
            if (dict_t.count(c) && window_counts[c] == dict_t[c]) {
                formed++;
            }
            while (l <= r && formed == required) {
                if (r - l + 1 < min_len) {
                    min_len = r - l + 1;
                    min_l = l;
                }
                char ch = s[l];
                window_counts[ch]--;
                if (dict_t.count(ch) && window_counts[ch] < dict_t[ch]) {
                    formed--;
                }
                l++;
            }
            r++;
        }
        return min_len == INT_MAX ? "" : s.substr(min_l, min_len);
    }
};
      
import java.util.*;

class Solution {
    public String minWindow(String s, String t) {
        if (s.length() == 0 || t.length() == 0) return "";
        Map<Character, Integer> dictT = new HashMap<>();
        for (char c : t.toCharArray()) {
            dictT.put(c, dictT.getOrDefault(c, 0) + 1);
        }
        int required = dictT.size();
        Map<Character, Integer> windowCounts = new HashMap<>();
        int l = 0, r = 0, formed = 0;
        int[] ans = {-1, 0, 0};
        
        while (r < s.length()) {
            char c = s.charAt(r);
            windowCounts.put(c, windowCounts.getOrDefault(c, 0) + 1);

            if (dictT.containsKey(c) && windowCounts.get(c).intValue() == dictT.get(c).intValue()) {
                formed++;
            }
            while (l <= r && formed == required) {
                if (ans[0] == -1 || r - l + 1 < ans[0]) {
                    ans[0] = r - l + 1;
                    ans[1] = l;
                    ans[2] = r;
                }
                char ch = s.charAt(l);
                windowCounts.put(ch, windowCounts.get(ch) - 1);
                if (dictT.containsKey(ch) && windowCounts.get(ch).intValue() < dictT.get(ch).intValue()) {
                    formed--;
                }
                l++;
            }
            r++;
        }
        return ans[0] == -1 ? "" : s.substring(ans[1], ans[2] + 1);
    }
}
      
var minWindow = function(s, t) {
    if (!s || !t) return "";
    let dictT = {};
    for (let c of t) dictT[c] = (dictT[c] || 0) + 1;
    let required = Object.keys(dictT).length;
    let l = 0, r = 0, formed = 0;
    let windowCounts = {};
    let ans = [Infinity, 0, 0];

    while (r < s.length) {
        let c = s[r];
        windowCounts[c] = (windowCounts[c] || 0) + 1;
        if (dictT[c] && windowCounts[c] === dictT[c]) {
            formed++;
        }
        while (l <= r && formed === required) {
            if (r - l + 1 < ans[0]) {
                ans = [r - l + 1, l, r];
            }
            let ch = s[l];
            windowCounts[ch]--;
            if (dictT[ch] && windowCounts[ch] < dictT[ch]) {
                formed--;
            }
            l++;
        }
        r++;
    }
    return ans[0] === Infinity ? "" : s.slice(ans[1], ans[2] + 1);
};

Problem Description

Given two strings, s and t, find the minimum window substring in s that contains all the characters from t (including duplicates). The substring must be contiguous. If there is no such substring, return the empty string "".
  • Each character in t must appear in the window at least as many times as it appears in t.
  • There is exactly one valid solution for each input.
  • Characters in s can be reused as long as they are within the window; you do not "consume" them for t.
Example:
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"

Thought Process

When first approaching this problem, it's natural to think about checking every possible substring of s to see if it contains all characters from t. However, this brute-force method is inefficient, especially for long strings.
Instead, we can recognize that the problem is about finding the smallest "window" in s that contains all the required characters. This hints at using a "sliding window" technique, where we expand and contract a window over s to efficiently check for valid substrings.
The key insight is to move two pointers (left and right) along s, expanding the window to include new characters and contracting it to remove unnecessary ones, always keeping track of the required characters from t.

Solution Approach

To solve this efficiently, we use the sliding window technique with two pointers:
  1. Count Characters in t: Use a hash map to store the frequency of each character in t. This lets us quickly check if our current window contains enough of each required character.
  2. Expand the Window: Move the right pointer to include new characters from s into the current window, updating counts as we go.
  3. Check for Valid Window: If the window contains all characters from t (with correct frequencies), try to shrink the window from the left to find the smallest possible valid window.
  4. Shrink the Window: Move the left pointer to remove unnecessary characters, updating counts and checking if the window still contains all required characters.
  5. Track the Minimum: Each time a valid window is found, compare its length to the minimum found so far and update if it's smaller.
Why use a hash map? Because it allows O(1) lookups and updates for character counts, making the window checks efficient.
Why two pointers? Because we need to both expand and contract the window to find the minimum substring that meets the requirements.

Example Walkthrough

Input: s = "ADOBECODEBANC", t = "ABC"
Step-by-step:
  1. Build a count map for t: {'A':1, 'B':1, 'C':1}
  2. Start with both pointers at the beginning. Expand right pointer until all required characters are included:
    • Right moves to 'A' (counts: {'A':1})
    • Right moves to 'D', 'O', 'B' (now have {'A':1,'B':1})
    • Continue to 'E', 'C' (now have {'A':1,'B':1,'C':1})
  3. Now, try to shrink from the left. Move left pointer forward, removing 'A', then 'D', then 'O', each time checking if the window is still valid. The first valid window is "ADOBEC".
  4. Continue expanding right, updating counts as you go, and repeat shrinking whenever the window is valid. Eventually, find "BANC" as the smallest valid window.
Result: "BANC" is returned because it's the shortest substring containing 'A', 'B', and 'C'.

Time and Space Complexity

Brute-force approach:
  • Check all substrings of s: O(N2) substrings, each checked for O(M) (length of t) characters → O(N2 * M) time.
  • Space: O(M) for storing t counts.
Optimized sliding window approach:
  • Time: O(N), where N is the length of s. Each character is visited at most twice (once by right, once by left pointer).
  • Space: O(M) for the hash maps (counts for t and the window).
The sliding window is much more efficient for large inputs.

Summary

The minimum window substring problem is elegantly solved using the sliding window technique, which efficiently expands and contracts a window over the input string. By keeping character counts in hash maps and moving two pointers, we avoid redundant checks and ensure optimal performance. The key insight is to only keep track of the necessary characters and minimize the window whenever possible, making the solution both fast and intuitive.