Minimum Window Substring (LC 76)

Pattern: Sliding Window + Frequency Map
Difficulty: Hard
Key Concept: Expand until the window covers all required characters, then shrink from the left as much as possible while still valid—track “how many required chars have satisfied count.”

Problem Statement

Given two strings s and t, 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 "".

Input

• s, t: String — t can be shorter or longer; lengths up to ~10⁵ in typical constraints

Output

• String — smallest-length contiguous substring of s covering multiset t, or ""

Example

• s = "ADOBECODEBANC", t = "ABC" → "BANC"
• s = "a", t = "a" → "a"
• s = "a", t = "aa" → ""

---

1. Algorithm & Pseudocode

Brute force

For every substring of s, check if it contains all of t’s letters with correct multiplicities.

best = null
for left from 0 to n-1:
    for right from left to n-1:
        if covers(s[left..right], t):
            best = shorter(best, s[left..right])
return best or ""

covers needs a fresh frequency count each time → very slow.

Optimal

• Build need[c] = required count from t.
• Sliding window on s with have[c] = count in window.
• formed = how many distinct characters from t have reached their required count in the window.
• When formed == requiredDistinct, try shrinking left.

need = frequency map of t
left = 0
formed = 0
requiredDistinct = number of keys in need with count>0
bestLen = infinity, bestL = 0

for right from 0 to n-1:
    c = s[right]
    add c to window counts
    if need[c] > 0 and windowCount[c] == need[c]:
        formed++
    while formed == requiredDistinct:
        update best window with [left, right]
        remove s[left] from window; adjust formed if broken
        left++

return slice or ""

---

2. Step-by-Step Analysis (Beginner-Friendly)

1. Why two pointers Once right includes enough characters, any shorter candidate for the same right must start later—so move left forward while valid.

2. Why formed instead of scanning the map Checking “all needs met” by scanning 128 keys every step is OK constant time, but formed makes the valid test O(1).

3. When formed increments Only when the count for character c just reached exactly need[c]—not when it exceeds.

4. When formed decrements When shrinking drops c’s count from need[c] down to need[c]-1—the requirement is broken.

5. Duplicates in t need stores multiplicities; the window must match counts, not just presence.

---

3. The Dry Run

Sample: s = "ABA", t = "AB".

right	window	have (A,B)	formed	shrink?	best
0	A	(1,0)	0	—	—
1	AB	(1,1)	2	yes	"AB" at [0,1]
shrink	B	(0,1)	1	stop
2	BA	(1,1)	2	yes	len 2 tie

Result: "AB" (or "BA" depending on shrink choices—both length 2).

ASCII

s: A B A
t: A B

   L R   -> valid, try shrink L
     L R -> still valid? need A: have 0 -> invalid
       R -> expand
     L R -> valid window "BA"

---

4. Java Solution

Brute Force

class Solution {
    public String minWindow(String s, String t) {
        int n = s.length();
        String best = "";
        for (int i = 0; i < n; i++) {
            int[] need = new int[128];
            for (int k = 0; k < t.length(); k++) {
                need[t.charAt(k)]++;
            }
            for (int j = i; j < n; j++) {
                need[s.charAt(j)]--;
                if (allNonPositive(need)) {
                    String cand = s.substring(i, j + 1);
                    if (best.isEmpty() || cand.length() < best.length()) {
                        best = cand;
                    }
                }
            }
        }
        return best;
    }

    private boolean allNonPositive(int[] need) {
        for (int v : need) {
            if (v > 0) {
                return false;
            }
        }
        return true;
    }
}

Time: O(n³) if allNonPositive scans 128 each time × O(n²) windows — still very slow; shown for contrast.
Space: O(1).

Optimal

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

        int[] need = 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[] window = new int[128];
        int formed = 0;
        int left = 0;
        int bestLen = Integer.MAX_VALUE;
        int bestL = 0, bestR = 0;

        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            window[c]++;

            if (need[c] > 0 && window[c] == need[c]) {
                formed++;
            }

            while (formed == required) {
                if (right - left + 1 < bestLen) {
                    bestLen = right - left + 1;
                    bestL = left;
                    bestR = right;
                }
                char cl = s.charAt(left);
                window[cl]--;
                if (need[cl] > 0 && window[cl] < need[cl]) {
                    formed--;
                }
                left++;
            }
        }

        return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestL, bestR + 1);
    }
}

Time: O(|s| + |t|) — each index visited a constant number of times.
Space: O(1) — fixed alphabet arrays (128).

---

5. The “Java vs. Others” Edge

• substring(begin, endExclusive) In Java 7+, substring copies chars (no huge memory sharing surprises like old JDKs).
• ASCII array vs HashMap For byte/ASCII char sets, int[128] avoids boxing and is faster—common senior optimization.
• Edge: t longer than s Quick length check can return early.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	O(n² · σ) or worse	O(1)	Re-scan needs per substring.
Optimal sliding window	O(n + m)	O(1)	n = |s|, m = |t|; σ constant map.