LeetCode 76 – Minimum Window Substring

Minimum Window Substring is the hardest sliding-window problem on most lists, and the difficulty is not the window — it is knowing when the window is valid without recounting it. The solution hinges on one counter that most people do not think to keep, and once you have it the whole thing is about fifteen lines.

The problem

Given strings s and t, return the shortest substring of s that contains every character of t, including duplicates. If there is no such substring, return "".

s = "ADOBECODEBANC", t = "ABC"   -> "BANC"
s = "a",  t = "a"                -> "a"
s = "a",  t = "aa"               -> ""      only one 'a' available
s = "ab", t = "b"                -> "b"
s = "ab", t = "A"                -> ""      case-sensitive

t = "aa" is the case that separates a working solution from a nearly-working one. Tracking which characters are present is not enough; you need how many.

Two pointers, and the invariant

The shape is standard: a right pointer that always advances, and a left pointer that catches up whenever it can. The right pointer grows the window until it is valid; the left pointer then shrinks it while it stays valid, recording the best as it goes.

ADOBECODEBANC   t = "ABC"

[ADOBEC]        valid   -> record, length 6
 [DOBEC]        invalid -> grow again
[ADOBECODEBA]   ...
      [CODEBA]  valid   -> record, length 6
         [BANC] valid   -> record, length 4   <- best

Each pointer only ever moves right, so the total work is O(|s|) even though the loops are nested. That is the argument to give when asked why this is not quadratic: it is not "the inner loop is short", it is "the inner pointer never goes backwards, so across the whole run it moves at most |s| times".

The counter that makes it work

Re-checking whether the window is valid costs O(128) or O(|t|) each time, and doing it on every step is what turns a clean idea into slow code. Instead keep a single integer:

need[c]   how many more of c the window still requires
          -- goes NEGATIVE for characters it has in surplus

missing   how many characters are still unmet, counting duplicates
          -- the window is valid exactly when missing == 0

The whole trick is in when missing changes. Taking a character in only helps if the window actually still needed it:

taking s[right]:   if need[c] > 0 then missing--       then need[c]--
dropping s[left]:  need[c]++       then if need[c] > 0 then missing++

A surplus 'A' pushes need['A'] to -1 and leaves missing alone, so giving that surplus back later also leaves it alone. Only the transition across zero matters. That is why need is allowed to go negative rather than being clamped — the sign is carrying the information.

In Java this collapses to a post-increment idiom worth recognising, since it appears in most published solutions: if (need[c]-- > 0) missing--; tests the old value and decrements in one step.

Java

class Solution {
    public String minWindow(String s, String t) {
        if (t.isEmpty() || s.length() < t.length()) return "";

        int[] need = new int[128];                      // ASCII, both cases
        for (char c : t.toCharArray()) need[c]++;

        int missing = t.length();                       // duplicates counted
        int bestStart = 0, bestLength = Integer.MAX_VALUE;

        for (int left = 0, right = 0; right < s.length(); right++) {
            // Only a character we still needed reduces `missing`.
            if (need[s.charAt(right)]-- > 0) missing--;

            while (missing == 0) {                      // valid -- shrink from the left
                if (right - left + 1 < bestLength) {
                    bestLength = right - left + 1;
                    bestStart = left;
                }
                // Giving this one back only breaks the window if it was not surplus.
                if (need[s.charAt(left)]++ == 0) missing++;
                left++;
            }
        }

        return bestLength == Integer.MAX_VALUE
                ? ""
                : s.substring(bestStart, bestStart + bestLength);
    }
}

new int[128] assumes ASCII, which this problem guarantees — say so rather than letting it pass unremarked. For arbitrary Unicode it becomes a Map<Character, Integer>, the logic is unchanged, and the constant factor gets worse.

Record bestStart and bestLength rather than slicing the string every time you improve. Substring allocation inside the loop is how an O(n) algorithm quietly becomes O(n²) in wall-clock terms.

Python

from collections import Counter


class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not t or len(s) < len(t):
            return ""

        need = Counter(t)
        missing = len(t)
        best_length, best_start = float("inf"), 0
        left = 0

        for right, c in enumerate(s):
            if need[c] > 0:
                missing -= 1
            need[c] -= 1                      # may go negative: that is the surplus

            while missing == 0:
                if right - left + 1 < best_length:
                    best_length, best_start = right - left + 1, left

                need[s[left]] += 1
                if need[s[left]] > 0:         # we just gave back one we needed
                    missing += 1
                left += 1

        return "" if best_length == float("inf") else s[best_start:best_start + best_length]

Counter returns 0 for a missing key instead of raising, which is what lets characters of s that never appear in t flow through the same two lines. Reaching for need[c] -= 1 on an absent key with a plain dict would throw.

Complexity

	Time	Space
Every substring	`O(\|s\|² · \|t\|)`	`O(\|t\|)`
Sliding window	`O(\|s\| + \|t\|)`	`O(1)` for ASCII

Each character of s is taken in once and given back at most once, so the pointers move 2|s| times total. The space is the alphabet, not the input, so it is O(1) under the ASCII constraint and O(|t|) in general.

The pattern

This is the general form of "shrinkable window with a validity condition", and the rest of the family is easier once it is written. Longest Substring Without Repeating Characters (3) shrinks while a duplicate is present. Permutation in String (567) and Find All Anagrams (438) are the same counting but with the window pinned to |t|, so the left pointer moves in lockstep rather than catching up. Longest Repeating Character Replacement (424) keeps a window valid on a budget instead of a requirement.

The distinction to carry away: a fixed-size window is a much simpler problem than a shrinkable one, and recognising which you have decides the shape of the loop before you write it.

What the interviewer is checking

That duplicates in t are counted, not just membership.
The single missing counter instead of re-validating the window.
That need is allowed to go negative, and why the sign carries meaning.
That you can argue O(n) from "neither pointer moves backwards".
The shrink loop being while, not if — several characters can leave at once.
t longer than s, no valid window, and case sensitivity.
That you record indices rather than slicing inside the loop.