Minimum Window Substring [Hard] — have/need Frequency Counter

Problem Statement

Given strings s and t, return the minimum window substring of s containing every character in t. Return "" if impossible.

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

Intuition

Sliding window with need map (char→count from t) and have counter. Expand right; when a char's count matches need, increment have. When have == len(need), shrink from left to minimize.

Solutions

C++

string minWindow(string s, string t) {
    unordered_map<char,int> need, win;
    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++){
        win[s[r]]++;
        if(need.count(s[r])&&win[s[r]]==need[s[r]]) have++;
        while(have==needed){
            if(r-l+1<minLen){minLen=r-l+1;start=l;}
            win[s[l]]--;
            if(need.count(s[l])&&win[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|)