Minimum Window Substring

Problem

Given strings s and t, return the smallest substring of s that contains every character of t (multiplicities included). If none exists, return "".

Constraints

• 1 ≤ s.length, t.length ≤ 10⁵

Approach — Sliding Window

This is a Sliding Window problem. The idea: keep a moving window over the sequence, expanding and shrinking it while tracking the answer in a single pass. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time.

Solution code

Python

class Solution:
    def minWindow(self, s, t):
        from collections import Counter
        need = Counter(t)
        missing = len(t)
        l = start = 0
        end = -1
        for r, ch in enumerate(s):
            if need[ch] > 0:
                missing -= 1
            need[ch] -= 1
            while missing == 0:
                if end == -1 or r - l < end - start:
                    start, end = l, r
                need[s[l]] += 1
                if need[s[l]] > 0:
                    missing += 1
                l += 1
        return s[start:end+1] if end != -1 else ""

Java

import java.util.HashMap;
import java.util.Map;

class Solution {
    public String minWindow(String s, String t) {
        if (s.length() < t.length()) return "";
        Map<Character, Integer> need = new HashMap<>();
        for (char c : t.toCharArray()) need.merge(c, 1, Integer::sum);
        int required = need.size(), formed = 0, l = 0, bestL = 0, bestLen = Integer.MAX_VALUE;
        Map<Character, Integer> have = new HashMap<>();
        for (int r = 0; r < s.length(); r++) {
            char c = s.charAt(r);
            int h = have.merge(c, 1, Integer::sum);
            if (need.containsKey(c) && h == need.get(c)) formed++;
            while (formed == required) {
                if (r - l + 1 < bestLen) { bestLen = r - l + 1; bestL = l; }
                char d = s.charAt(l++);
                int hd = have.merge(d, -1, Integer::sum);
                if (need.containsKey(d) && hd < need.get(d)) formed--;
            }
        }
        return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestL, bestL + bestLen);
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.