Google — Minimum Window Substring (Sliding Window + Frequency Map)

Problem (Google Very Frequent)

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

Example:

s = "ADOBECODEBANC", t = "ABC"
→ "BANC"

Key Insight — Two-Pointer with Have/Need Counters

Track need (char frequencies in t) and window (current window frequencies). have = number of distinct chars satisfying their required count.

Expand right until have == need
Contract left to minimize window while have == need

Solutions

Python

from collections import Counter

def minWindow(s: str, t: str) -> str:
    if not t: return ""
    need = Counter(t)
    window = {}
    have, required = 0, len(need)
    l = 0
    best = (float('inf'), 0, 0)

    for r, c in enumerate(s):
        window[c] = window.get(c, 0) + 1
        if c in need and window[c] == need[c]:
            have += 1
        while have == required:
            if r - l + 1 < best[0]:
                best = (r - l + 1, l, r)
            lc = s[l]
            window[lc] -= 1
            if lc in need and window[lc] < need[lc]:
                have -= 1
            l += 1

    return s[best[1]:best[2]+1] if best[0] != float('inf') else ""

JavaScript

function minWindow(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, req=need.size, l=0, res="", mn=Infinity;
    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===req) {
            if (r-l+1<mn){mn=r-l+1;res=s.slice(l,r+1);}
            const lc=s[l++]; win.set(lc,win.get(lc)-1);
            if (need.has(lc)&&win.get(lc)<need.get(lc)) have--;
        }
    }
    return res;
}

Java

import java.util.*;
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,req=need.size(),l=0,mn=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==req) {
            if (r-l+1<mn){mn=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--;
        }
    }
    return mn==Integer.MAX_VALUE?"":s.substring(start,start+mn);
}

C++

#include <unordered_map>
#include <string>
using namespace std;
string minWindow(string s, string t) {
    unordered_map<char,int> need, win;
    for (char c:t) need[c]++;
    int have=0,req=need.size(),l=0,mn=INT_MAX,start=0;
    for (int r=0;r<(int)s.size();r++) {
        char c=s[r]; win[c]++;
        if (need.count(c)&&win[c]==need[c]) have++;
        while (have==(int)req) {
            if (r-l+1<mn){mn=r-l+1;start=l;}
            char lc=s[l++]; win[lc]--;
            if (need.count(lc)&&win[lc]<need[lc]) have--;
        }
    }
    return mn==INT_MAX?"":s.substr(start,mn);
}

C

/* C: frequency arrays for 128 ASCII chars, have/need counters */

Complexity

Approach	Time	Space
Two pointer	O(n+m)	O(n+m)