Minimum Window Substring [Hard] — Sliding Window with Frequency Map

Problem Statement

Given strings s and t, return the minimum window substring of s that contains all characters of t. Return "" if none exists.

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

Intuition

Expand right until window contains all of t. Then shrink from left while still valid, tracking minimum. Use a counter of needed characters and a have/need comparison.

Solutions

C++

string minWindow(string s, string t) {
    unordered_map<char,int> need, window;
    for (char c:t) need[c]++;
    int have=0, needed=need.size(), l=0, minLen=INT_MAX, start=0;
    for (int r=0;r<s.size();r++) {
        window[s[r]]++;
        if (need.count(s[r])&&window[s[r]]==need[s[r]]) have++;
        while (have==needed) {
            if (r-l+1<minLen){minLen=r-l+1;start=l;}
            window[s[l]]--;
            if (need.count(s[l])&&window[s[l]]<need[s[l]]) have--;
            l++;
        }
    }
    return minLen==INT_MAX?"":s.substr(start,minLen);
}

Java

public String minWindow(String s, String t) {
    Map<Character,Integer> need=new HashMap<>(), win=new HashMap<>();
    for (char c:t.toCharArray()) need.merge(c,1,Integer::sum);
    int have=0,needed=need.size(),l=0,minLen=Integer.MAX_VALUE,start=0;
    for (int r=0;r<s.length();r++) {
        char c=s.charAt(r);
        win.merge(c,1,Integer::sum);
        if (need.containsKey(c)&&win.get(c).equals(need.get(c))) have++;
        while (have==needed){
            if(r-l+1<minLen){minLen=r-l+1;start=l;}
            char lc=s.charAt(l);
            win.merge(lc,-1,Integer::sum);
            if(need.containsKey(lc)&&win.get(lc)<need.get(lc))have--;
            l++;
        }
    }
    return minLen==Integer.MAX_VALUE?"":s.substring(start,start+minLen);
}

JavaScript

var minWindow = function(s, t) {
    const need=new Map(), win=new Map();
    for (const c of t) need.set(c,(need.get(c)||0)+1);
    let have=0,needed=need.size,l=0,minLen=Infinity,start=0;
    for (let r=0;r<s.length;r++) {
        const c=s[r]; win.set(c,(win.get(c)||0)+1);
        if(need.has(c)&&win.get(c)===need.get(c)) have++;
        while(have===needed){
            if(r-l+1<minLen){minLen=r-l+1;start=l;}
            const lc=s[l]; win.set(lc,win.get(lc)-1);
            if(need.has(lc)&&win.get(lc)<need.get(lc))have--;
            l++;
        }
    }
    return minLen===Infinity?"":s.slice(start,start+minLen);
};

Python

from collections import Counter, defaultdict

def minWindow(s: str, t: str) -> str:
    need = Counter(t)
    window = defaultdict(int)
    have, needed = 0, len(need)
    l, min_len, start = 0, float('inf'), 0
    for r, c in enumerate(s):
        window[c] += 1
        if c in need and window[c] == need[c]:
            have += 1
        while have == needed:
            if r - l + 1 < min_len:
                min_len, start = r - l + 1, l
            window[s[l]] -= 1
            if s[l] in need and window[s[l]] < need[s[l]]:
                have -= 1
            l += 1
    return '' if min_len == float('inf') else s[start:start+min_len]

Complexity

Time: O(|s| + |t|)
Space: O(|s| + |t|)