Minimum Window Substring

Free with account Updated Nov 19, 2026 · 6 min read
On this page

    Problem statement

    Given two strings s and t, return the shortest contiguous substring of s that contains every character of t, including repeats. If t has two A's, the window needs at least two A's. If no such window exists, return an empty string.

    The hardest of the standard sliding-window problems, and a common "can you keep your invariants straight under pressure" question. The structure is: expand until valid, shrink while valid, and track validity in O(1). Original problem: LeetCode 76.

    Example

    The shortest window of ADOBECODEBANC that contains A, B and C is BANC, length 4.
    The shortest window of ADOBECODEBANC that contains A, B and C is BANC, length 4.
    Input:  s = "ADOBECODEBANC", t = "ABC"
    Output: "BANC"
    Input:  s = "a", t = "aa"
    Output: ""        # s has only one 'a'

    Constraints (assumed)

    • 1 ≤ |s|, |t| ≤ 100,000.
    • Upper- and lowercase English letters.

    What this question tests

    • The expand–shrink form of the sliding window.
    • Tracking "is the window valid?" in O(1) per step instead of comparing whole maps.
    • Correct handling of repeated characters in t.

    Questions to ask first

    1. Do repeats in t matter? (Here: yes; "AAB" needs two A's.)
    2. Case sensitive? (Here: yes.)
    3. If several shortest windows exist, which one? (Here: any; the code returns the first.)
    4. Return the window or its length? (Here: the window, so track its start.)