LeetCode 76 Minimum Window Substring: The Sliding Window Masterclass

Minimum Window Substring is the problem that turns sliding window from a trick into a technique. It is tagged Hard, appears on Blind 75 and NeetCode 150, and shows up regularly in reported interviews at companies such as Amazon, Google, Meta, Microsoft and Uber. It is also the cleanest example of the variable-size window: a window that grows to become valid and shrinks to become optimal. Once you understand why it works and how the counters stay in sync, a whole family of problems collapses into one template.

The Problem: Smallest Substring Containing All of t

Given strings s (length m) and t (length n), return the minimum-length substring of s that contains every character of t, including duplicates. If no such substring exists, return the empty string. The test cases guarantee the answer is unique. Constraints: 1 <= m, n <= 10^5, upper- and lowercase English letters.

Three words carry the difficulty. Substring means contiguous, which is what makes a window possible. Contains means order inside the window does not matter. Including duplicates means you compare counts, not sets.

Brute Force and Why It Fails

Check every substring s[i..j], count its characters, compare against the counts of t. There are O(m²) substrings and each check costs up to O(m) to count (or O(1) amortised if you extend j incrementally for a fixed i). That gives O(m²) at best: about 10¹⁰ operations for m = 10⁵. Far too slow.

The waste is obvious once you see it. For a fixed start i, as soon as s[i..j] is valid, every longer window from i is also valid and worse. And when you move from start i to i + 1, the end that first makes the window valid can only move right, never left. That monotonicity is precisely what the two-pointer window exploits.

The Core Idea: Expand to Become Valid, Shrink to Become Minimal

Maintain a window s[left..right]. Two moves:

1. Expand. Move right one step and add s[right] to the window. Keep doing this until the window contains all of t.
2. Shrink. While the window is still valid, record it if it is the smallest so far, then remove s[left] and move left one step. Stop as soon as the window becomes invalid.

Then go back to expanding. When right reaches the end of s, you are done.

Why can you never miss the optimal window? Let the optimal window be s[L..R]. First, left cannot move past L before right reaches R: moving left from L to L + 1 requires the window s[L..right] to be valid for some right < R, which would be a valid window shorter than the optimum. Impossible. So when right arrives at R, the window s[left..R] contains s[L..R] and is valid. The shrink loop then advances left, and every intermediate window s[k..R] with k <= L still contains the optimum, so the loop keeps going until left == L and records it.

Checking Validity in O(1): The need/have Counters

The naive validity check compares the window's frequency map with t's map: O(52) per step for letters, which is technically constant but clumsy, and it scales badly with larger alphabets. The standard trick keeps a single integer that tracks how many requirements are currently satisfied.

• req[c]: how many of character c the window must contain (from t).
• window[c]: how many c the window currently contains.
• need: number of distinct characters in t. Fixed.
• have: number of distinct characters c with window[c] >= req[c].

The window is valid exactly when have == need. The trick is in how have changes:

• When adding c: increment window[c]. If now window[c] == req[c], increment have. It just crossed the threshold.
• When removing c: if window[c] == req[c] before the decrement, decrement have. It is about to fall below. Then decrement window[c].

Using == rather than >= is essential. If t = "AB" and the window picks up a third A, window[A] goes from 2 to 3. With >=, you would increment have again and overcount. Only the crossing matters.

The single-counter variant

A popular alternative keeps one map req and one integer missing = len(t) (total characters still missing, counting duplicates). Adding c: if req[c] > 0, decrement missing; then decrement req[c] (it can go negative, meaning surplus). Removing c: increment req[c]; if it becomes positive, increment missing. The window is valid when missing == 0. It is shorter, but the negative counts are harder to explain under pressure. I recommend need/have in interviews because each variable has an obvious meaning.

Minimum Window Substring Code: Python, Java and C++

from collections import Counter, defaultdict

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not t or len(t) > len(s):
            return ""
        req = Counter(t)
        need = len(req)
        window = defaultdict(int)
        have = 0
        best_len, best_l = float("inf"), 0
        left = 0
        for right, c in enumerate(s):
            window[c] += 1
            if c in req and window[c] == req[c]:
                have += 1
            while have == need:
                if right - left + 1 < best_len:
                    best_len, best_l = right - left + 1, left
                d = s[left]
                if d in req and window[d] == req[d]:
                    have -= 1
                window[d] -= 1
                left += 1
        return "" if best_len == float("inf") else s[best_l:best_l + best_len]

class Solution {
    public String minWindow(String s, String t) {
        if (t.length() == 0 || t.length() > s.length()) return "";
        int[] req = new int[128];
        int need = 0;
        for (char c : t.toCharArray()) {
            if (req[c] == 0) need++;
            req[c]++;
        }
        int[] window = new int[128];
        int have = 0, left = 0;
        int bestLen = Integer.MAX_VALUE, bestL = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            window[c]++;
            if (req[c] > 0 && window[c] == req[c]) have++;
            while (have == need) {
                if (right - left + 1 < bestLen) {
                    bestLen = right - left + 1;
                    bestL = left;
                }
                char d = s.charAt(left);
                if (req[d] > 0 && window[d] == req[d]) have--;
                window[d]--;
                left++;
            }
        }
        return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestL, bestL + bestLen);
    }
}

#include <string>
#include <climits>
using namespace std;

class Solution {
public:
    string minWindow(string s, string t) {
        if (t.empty() || t.size() > s.size()) return "";
        int req[128] = {0}, window[128] = {0};
        int need = 0;
        for (char c : t) {
            if (req[(unsigned char)c]++ == 0) need++;
        }
        int have = 0, left = 0, bestLen = INT_MAX, bestL = 0;
        for (int right = 0; right < (int)s.size(); ++right) {
            unsigned char c = s[right];
            if (++window[c] == req[c] && req[c] > 0) have++;
            while (have == need) {
                if (right - left + 1 < bestLen) {
                    bestLen = right - left + 1;
                    bestL = left;
                }
                unsigned char d = s[left];
                if (req[d] > 0 && window[d] == req[d]) have--;
                window[d]--;
                left++;
            }
        }
        return bestLen == INT_MAX ? "" : s.substr(bestL, bestLen);
    }
};

Fixed-size arrays of 128 are faster than hash maps and fine for ASCII. In Python a Counter is idiomatic. Storing (best_l, best_len) instead of slicing a new substring on every improvement keeps the loop O(1) per step; slicing inside the loop would add O(m) per improvement and could degrade the worst case.

Full Dry Run: s = "ADOBECODEBANC", t = "ABC"

req = {A:1, B:1, C:1}, need = 3. Indices:

Steps 15 to 17 deserve care. The window ODEBANC (indices 6 to 12) has length 7, not smaller than 6. Remove O: DEBANC, length 6, still not strictly smaller. Remove D: EBANC, length 5, which is smaller, so best becomes EBANC. Remove E: BANC, length 4, best becomes BANC. Removing B then makes have drop to 2 and the shrink loop exits. right is at the end, so we return BANC.

Notice step 10: removing a B did not reduce have, because the window had two B's and only one is required. The check window[d] == req[d] before decrementing was false (2 != 1). That is the duplicate-handling logic doing its job.

Complexity: Why the Nested Loop Is Still Linear

The while inside the for looks quadratic. It is not. left starts at 0 and only increases, and it never passes right + 1. So across the entire run the inner loop body executes at most m times in total. The outer loop runs m times. Total pointer moves: at most 2m. Add O(n) to count t.

This "amortised" argument is worth stating explicitly in the interview, because some interviewers ask "isn't that O(m²)?" just to see whether you can defend it.

Optimisation: filter s first

When s is long and most of its characters are not in t, you can precompute a list of (index, char) pairs for only the characters that appear in t, and slide the window over that list. Window length is still computed with the original indices. The complexity bound stays O(m + n), but the constant factor drops when t uses few distinct characters. This is LeetCode's own "optimised sliding window" approach. Mention it as a refinement, not as your main solution.

The Reusable Sliding Window Template

Strip LC 76 down to its skeleton and you get a template that covers most variable-size window problems:

def sliding_window(s):
    state = init_state()
    left = 0
    best = initial_best()
    for right, c in enumerate(s):
        add(state, c)                    # expand
        while window_needs_shrinking(state):
            # for SHORTEST valid window: record here, then remove
            remove(state, s[left])
            left += 1
        # for LONGEST valid window: record here (window is now valid)
    return best

Two flavours, and mixing them up is the most common template mistake:

Template reuse: three problems in a few lines each

LC 567 Permutation in String (does s2 contain a permutation of s1?): exactly LC 76's need/have logic with a fixed window of size len(s1). Return true as soon as have == need and the window length equals len(s1). LC 438 is the same, collecting every start index.

LC 209 Minimum Size Subarray Sum (positive integers): state is a running sum; shrink while sum >= target, recording the length first. Shortest-valid flavour.

LC 3 Longest Substring Without Repeating Characters: state is a character count; shrink while the newest character's count exceeds 1; record after the loop. Longest-valid flavour. Full walkthrough in LeetCode 3 explained.

def check_inclusion(s1: str, s2: str) -> bool:   # LC 567
    from collections import Counter, defaultdict
    req, window = Counter(s1), defaultdict(int)
    need, have, left = len(req), 0, 0
    for right, c in enumerate(s2):
        window[c] += 1
        if c in req and window[c] == req[c]:
            have += 1
        if right - left + 1 > len(s1):           # keep size fixed
            d = s2[left]
            if d in req and window[d] == req[d]:
                have -= 1
            window[d] -= 1
            left += 1
        if have == need:
            return True
    return False

In LC 567 the window size is fixed at len(s1), so have == need means the window's counts match s1's exactly: the window cannot hold surplus characters when every requirement is met and the total length equals len(s1). The broader catalogue of window problems lives in sliding window problems explained, and the fixed-size window with a monotonic deque is covered in LeetCode 239 Sliding Window Maximum.

Bugs That Fail Hidden Test Cases

• Using >= when incrementing have. Overcounts on surplus characters. Use == exactly at the crossing.
• Decrementing window[d] before checking. The check "was this requirement exactly met?" must happen before the decrement, or compare against req[d] - 1 after it. Pick one and be consistent.
• Counting characters not in t toward have. With arrays, a character outside t has req[c] == 0 while window[c] is at least 1 after adding, so window[c] == req[c] can never fire; the extra req[c] > 0 check is just for readability. In hash-map versions, keep an explicit c in req check anyway: it states the intent, and with a defaultdict a bare lookup like req[c] would silently insert every unrelated character as a key.
• Using a set instead of counts. Fails t = "aa".
• Recording after shrinking. For the shortest-window flavour, record inside the loop before removing s[left]; after the loop the window is invalid.
• Off-by-one in the answer. Length is right - left + 1. Java's substring(begin, end) is end-exclusive; C++'s substr(pos, len) takes a length.
• Using char as an array index in C++. Plain char may be signed; cast to unsigned char to be safe with non-ASCII input.
• Not handling len(t) > len(s). The loop handles it correctly anyway, but an early return is cleaner and shows awareness.

Interview Playbook for Minimum Window Substring

This is a Hard problem where the interviewer expects you to arrive at the optimal solution, so the main risk is bugs under time pressure, not the idea. A good sequence:

1. Clarify. Case-sensitive? Character set? Do duplicates in t count? What to return when there is no answer, and on ties?
2. Brute force in one sentence, with its complexity.
3. State the monotonic property: a valid window stays valid when extended, so expand to become valid and shrink to become minimal.
4. Explain need/have before coding. This is where interviewers decide whether you really understand it.
5. Code carefully, naming variables after their meaning.
6. Dry run on a small case with a duplicate, such as s = "AAB", t = "AB" (answer AB).
7. Complexity with the amortised argument.

Follow-ups to prepare

• "What if t can contain any Unicode character?" Use a hash map instead of a fixed array; complexity stays O(m + n) expected.
• "What if s is a stream and you cannot store it?" You must keep the current window's characters to shrink from the left, so memory is O(window size). You can still report the best window's start index and length as you go.
• "Return all minimum windows" or "count windows that contain all of t": count with the "for each right, every left up to the last valid one works" trick.
• "Why not compare maps each step?" It works, at O(alphabet) per step; need/have is the cleaner O(1) check.

Practising your narration matters as much as the code here. The technique in thinking out loud during coding interviews helps you explain need/have while typing. For more string patterns that combine counting and windows, see string interview problems and patterns and hashing and hashmap problems.

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.