Problem statement

Given strings s and t, return the minimum-length window substring of s that contains every character of t (including duplicates). If no such substring exists, return "". If several minimal windows exist, return the leftmost one.

Example 1

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"

Example 2

Input: s = "a", t = "aa"
Output: ""
Explanation: Both a's of t must be in the window.

Constraints

• 1 <= s.length <= 40
• 1 <= t.length <= 5
• Lowercase English letters.

Hints for Minimum Window Substring

1. Hint 1

   Expand the right edge until the window covers t, then shrink from the left while it still covers.

2. Hint 2

   Track how many distinct required characters are currently satisfied.

How to solve Minimum Window Substring

Grow the window rightwards until it covers every character of t (counting duplicates), then shrink it from the left for as long as it still covers. Every time the window is valid, it is the shortest one ending at that right edge — so recording it at each such moment finds the global minimum.

Approach

1. Count the characters t requires, and note how many distinct characters must be satisfied.
2. Extend the right edge, incrementing the window's count for the incoming character; when a character's count reaches its requirement, one more distinct requirement is satisfied.
3. While all requirements are satisfied, record the window if it beats the best, then shrink from the left.
4. Shrinking un-satisfies a requirement only when a count drops below what is needed.
5. Return the best window, or the empty string if none was ever valid.

Why it works

Tracking a count of satisfied distinct characters turns the validity test into a single comparison, instead of scanning the whole frequency table at every step — that is what keeps the sweep linear. The shrink loop is what makes each recorded window minimal for its right edge: it stops exactly when removing one more character would break coverage. Recording only on a strictly smaller length keeps the leftmost among equally short windows.

Complexity

• Time — O(|s| + |t|)
• Space — O(1) over a fixed alphabet

Pitfalls

• Duplicates in t matter: "aa" needs two as, so counts must be compared, not mere presence.
• Decrement the satisfied counter only when a count falls below the requirement — going from 3 to 2 when 2 are needed changes nothing.
• Record the window before shrinking past validity, not after.
• No valid window means the empty string, not a sentinel.

Reference solution

Python

def minWindow(s: str, t: str) -> str:
    from collections import Counter
    need = Counter(t)
    required = len(need)
    have = {}
    formed = 0
    l = 0
    best_len = float("inf")
    best_l = 0
    for r, ch in enumerate(s):
        have[ch] = have.get(ch, 0) + 1
        if ch in need and have[ch] == need[ch]:
            formed += 1
        while formed == required:
            if r - l + 1 < best_len:
                best_len = r - l + 1
                best_l = l
            lc = s[l]
            have[lc] -= 1
            if lc in need and have[lc] < need[lc]:
                formed -= 1
            l += 1
    return "" if best_len == float("inf") else s[best_l:best_l + best_len]

Java

public static String minWindow(String s, String t) {
    int[] need = new int[128];
    int[] win = new int[128];
    int required = 0;
    for (int i = 0; i < t.length(); i++) {
        char c = t.charAt(i);
        if (need[c] == 0) required++;
        need[c]++;
    }
    int have = 0, l = 0, bestLen = -1, bestStart = 0;
    for (int r = 0; r < s.length(); r++) {
        char c = s.charAt(r);
        win[c]++;
        if (need[c] > 0 && win[c] == need[c]) have++;
        while (have == required) {
            if (bestLen == -1 || r - l + 1 < bestLen) {
                bestLen = r - l + 1;
                bestStart = l;
            }
            char d = s.charAt(l);
            win[d]--;
            if (need[d] > 0 && win[d] < need[d]) have--;
            l++;
        }
    }
    return bestLen == -1 ? "" : s.substring(bestStart, bestStart + bestLen);
}

C++

string minWindow(string s, string t) {
    vector<int> need(128, 0), win(128, 0);
    int required = 0;
    for (char c : t) {
        if (need[(unsigned char) c] == 0) required++;
        need[(unsigned char) c]++;
    }
    int have = 0, l = 0, bestLen = -1, bestStart = 0;
    for (int r = 0; r < (int) s.size(); r++) {
        int c = (unsigned char) s[r];
        win[c]++;
        if (need[c] > 0 && win[c] == need[c]) have++;
        while (have == required) {
            if (bestLen == -1 || r - l + 1 < bestLen) {
                bestLen = r - l + 1;
                bestStart = l;
            }
            int d = (unsigned char) s[l];
            win[d]--;
            if (need[d] > 0 && win[d] < need[d]) have--;
            l++;
        }
    }
    return bestLen == -1 ? "" : s.substr(bestStart, bestLen);
}

JavaScript

var minWindow = function(s, t) {
    const need = new Map();
    for (const ch of t) need.set(ch, (need.get(ch) || 0) + 1);
    const required = need.size;
    const have = new Map();
    let formed = 0, l = 0, bestLen = Infinity, bestL = 0;
    for (let r = 0; r < s.length; r++) {
        const ch = s[r];
        have.set(ch, (have.get(ch) || 0) + 1);
        if (need.has(ch) && have.get(ch) === need.get(ch)) formed++;
        while (formed === required) {
            if (r - l + 1 < bestLen) { bestLen = r - l + 1; bestL = l; }
            const lc = s[l];
            have.set(lc, have.get(lc) - 1);
            if (need.has(lc) && have.get(lc) < need.get(lc)) formed--;
            l++;
        }
    }
    return bestLen === Infinity ? "" : s.slice(bestL, bestL + bestLen);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Prefix and Suffix Search Hard
• Recover a Tree From Preorder Traversal Hard
• Minimum Time to Revert Word to Initial State II Hard
• Maximum Product of the Length of Two Palindromic Substrings Hard
• Longest Chunked Palindrome Decomposition Hard
• K-Similar Strings Hard