Free lesson · DSA Mastery - Interview Prep, End to End

Minimum Window Substring

Medium8 min readdsasliding-window

Minimum Window Substring

Minimum Window Substring is the keystone of the module - the problem most often labeled "hard," and the one that brings together everything: the shortest-valid-window template, a frequency-map target, and the match-counter engine first seen in Find All Anagrams. Given strings s and t, find the shortest substring of s that contains all characters of t (including duplicates). We climb three approaches: brute force (check every substring's coverage, O(n²·Σ)), the optimal sliding window with a need-map and a "have/need" match counter (O(n)), and a filtered-window optimization for sparse alphabets.

If you internalize one hard sliding-window solution, make it this one - its "expand to satisfy, shrink while valid, track minimum" structure is the shortest-window template at full strength.

The Problem

Given two strings s and t of lengths m and n, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

The test cases are generated such that the answer is unique.

Example 1:

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

Explanation: The minimum window "BANC" includes 'A', 'B', and 'C'.

Example 2:

Input:  s = "a", t = "a"
Output: "a"

Example 3:

Input:  s = "a", t = "aa"
Output: ""

Explanation: Both 'a's from t must be in the window, but s has only one 'a'.

Constraints:

• m == s.length, n == t.length
• 1 <= m, n <= 10^5
• s and t consist of uppercase and lowercase English letters.

Approaches Overview

The match counter is the engine: track how many required characters are currently satisfied. When all are, the window is valid; then shrink to find the minimum.

Approach 1: Brute Force

The Idea

For every substring of s, check whether it covers t's character counts. Track the shortest covering substring.

Logic Flowchart

graph TD
    A["need = counts of t<br/>best = none"] --> B["For start i = 0 to m-1"]
    B --> C["For end j = i to m-1"]
    C --> D["counts of s[i..j]"]
    D --> E{"covers need?"}
    E -->|Yes| F["best = shorter of (best, s[i..j]); break"]
    E -->|No| G{"More j?"}
    G -->|Yes| C
    G -->|No| H["(start done)"]
    F --> I{"More i?"}
    H --> I
    I -->|Yes| B
    I -->|No| J["Return best or ''"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style D fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style E fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style F fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style G fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style H fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style I fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style J fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows the brute-force approach. For each start, we extend the end building character counts until the window covers the target multiset, recording the shortest covering substring. Examining all substrings with coverage checks is far too slow.

Code

public static String minWindowBrute(String s, String t) {
    int[] need = new int[128];
    for (char c : t.toCharArray()) need[c]++;
    int m = s.length(), bestLen = Integer.MAX_VALUE, bestStart = -1;

    for (int i = 0; i < m; i++) {
        int[] win = new int[128];
        for (int j = i; j < m; j++) {
            win[s.charAt(j)]++;
            if (covers(win, need)) {
                if (j - i + 1 < bestLen) { bestLen = j - i + 1; bestStart = i; }
                break;
            }
        }
    }
    return bestStart == -1 ? "" : s.substring(bestStart, bestStart + bestLen);
}

private static boolean covers(int[] win, int[] need) {
    for (int c = 0; c < 128; c++) if (win[c] < need[c]) return false;
    return true;
}

This Java code checks every substring by extending an end pointer until the window covers the target counts, recording the shortest. The coverage scan per step makes it far too slow.

Complexity

Time: O(m²·Σ). Space: O(Σ).

The window restarts at each i, and coverage is re-scanned. A single forward-only window with a match counter fixes both.

Approach 2: Sliding Window + Match Counter - Optimal

The Idea

Build need[c] = required count of each character, and required = number of distinct characters in t. Slide a window with have[c] counts and a formed counter = how many distinct required characters currently have have[c] >= need[c]. Expand right; when a character's have reaches its need, increment formed. When formed == required, the window covers t - shrink from left while still covered, recording the minimum window, and decrement formed when a required character drops below its need. One pass: O(m + n).

Logic Flowchart

graph TD
    A["need = counts of t<br/>required = distinct in t<br/>have={}, formed=0, left=0"] --> B["For right = 0 to m-1"]
    B --> C["c = s[right]; have[c]++"]
    C --> D{"c needed AND have[c]==need[c]?"}
    D -->|Yes| E["formed++"]
    D -->|No| F["continue"]
    E --> G{"formed == required?"}
    F --> G
    G -->|Yes| H["record window if shorter<br/>remove s[left]; if it drops a<br/>required char below need: formed--<br/>left++"]
    H --> G
    G -->|No| I{"More?"}
    I -->|Yes| B
    I -->|No| J["Return best window or ''"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style D fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style E fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style G fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style H fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style I fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style J fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows the optimal window. We track required character counts and how many distinct required characters are currently satisfied. Expanding the window increments a satisfied count when a character reaches its needed amount. When all required characters are satisfied, we shrink from the left, recording the smallest covering window and reducing the satisfied count when a required character drops below its need.

Code

public static String minWindow(String s, String t) {
    if (s.length() < t.length()) return "";
    int[] need = new int[128];
    int required = 0;
    for (char c : t.toCharArray()) {
        if (need[c] == 0) required++;
        need[c]++;
    }

    int[] have = new int[128];
    int formed = 0, left = 0;
    int bestLen = Integer.MAX_VALUE, bestStart = 0;

    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        have[c]++;
        if (need[c] > 0 && have[c] == need[c]) formed++;

        while (formed == required) {                 // valid: shrink to minimize
            if (right - left + 1 < bestLen) {
                bestLen = right - left + 1;
                bestStart = left;
            }
            char lc = s.charAt(left);
            have[lc]--;
            if (need[lc] > 0 && have[lc] < need[lc]) formed--;
            left++;
        }
    }
    return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestStart, bestStart + bestLen);
}

// Usage:
// minWindow("ADOBECODEBANC", "ABC") -> "BANC"
// minWindow("a", "a")               -> "a"
// minWindow("a", "aa")              -> ""

This Java code builds the required character counts and the number of distinct required characters. It expands a window, incrementing a satisfied counter when a character reaches its needed count. When all required characters are satisfied, it shrinks from the left, recording the smallest covering window and decrementing the counter when a required character falls below its need. It returns the shortest window, or empty if none.

Step-by-Step Walkthrough

A frame-by-frame trace on s = "ADOBECODEBANC", t = "ABC" (required = 3). Showing the key moments where the window becomes valid and shrinks:

graph LR
    F0["expand to 'ADOBEC'<br/>have A,B,C<br/>formed=3 valid<br/>best='ADOBEC' len6"]
    F1["shrink: drop A<br/>formed=2, expand...<br/>'DOBECODEBA' covers<br/>shrink → 'ODEBANC'? "]
    F2["expand to '...BANC'<br/>formed=3 again<br/>shrink to 'BANC' len4<br/>best='BANC'"]
    F0 --> F1 --> F2

    style F0 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F1 fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style F2 fill:#16a34a,stroke:#10b981,color:#f1f5f9

This walkthrough traces A D O B E C O D E B A N C seeking the shortest window covering A B C. The window first becomes valid at A D O B E C, length six. Shrinking drops the leading A, breaking validity, and the window expands again. Eventually the window B A N C covers all three with length four, the minimum.

Result: "BANC".

Complexity

Time: O(m + n) - each character of s enters and leaves once; building need is O(n). Space: O(Σ) - fixed 128-entry arrays.

Approach 3: Filtered Window (Sparse Alphabet)

The Idea

When t is short relative to s, most of s's characters are irrelevant. Pre-filter s to a list of (index, char) pairs containing only characters that appear in t, then run the same window over that filtered list. This skips irrelevant characters during shrinking, a constant-factor speedup when the filtered list is much shorter than s. Same asymptotics.

Complexity

Time: O(m + n), faster in practice when t's characters are sparse in s. Space: O(Σ + filtered size).

Complexity Comparison

The match-counter window is the definitive solution. The formed/required counter - counting distinct satisfied requirements, not raw matches - is what keeps validity checking O(1) and is the same idea as the anagram match counter, scaled to "cover, with duplicates."

Variations & Follow-ups

How is this the shortest-window template?

It's "expand to satisfy (formed == required), then shrink while still valid, tracking the minimum" - the exact shortest-valid shape from Minimum Size Subarray Sum, but with a multiset-coverage condition instead of a sum threshold.

How does the match counter differ from Find All Anagrams?

There, the window was fixed-width and required an exact count match (anagram). Here, the window is dynamic and requires at least the needed counts (coverage, with extras allowed). formed counts distinct requirements met, so extras don't break validity.

What if t had characters not in s?

formed never reaches required; the answer is "" (Example 3 is the duplicate-shortage version).

Why track required as distinct characters, not t.length()?

Because a character needing count 3 should bump formed once (when it reaches 3), not three times. formed counts satisfied distinct requirements.

What about edge cases?

• No covering window: Return "".
• t longer than s: Return "".
• s == t: The whole string is the answer.
• Duplicates in t: need counts enforce them (Example 3).

Common Interview Pitfalls

• Counting raw matches instead of satisfied requirements. Use formed == required over distinct characters.
• Decrementing formed at the wrong moment. Only when a required character drops below its need on removal.
• Recording the window outside the shrink loop. Record inside while (formed == required), before shrinking.
• Forgetting the no-answer sentinel. Return "" when no window covers t.

Why This Problem Matters

Minimum Window Substring is the capstone shortest-window problem and the fullest expression of the match-counter engine. It synthesizes the dynamic-window template, multiset-coverage tracking, and the distinct-requirements counter - patterns seeded across the whole module. It's among the most-asked hard interview problems precisely because it tests whether you can compose these pieces under pressure.

The next topic, Minimum Window Subsequence, looks deceptively similar but is fundamentally different: it asks for a subsequence, not a substring - and because subsequences are gappy, the sliding window doesn't apply. We'll see the two-pointer forward-then-backward scan (and the DP alternative) that the problem actually requires.

Back to DSA Mastery - Interview Prep, End to End