076. Minimum Window Substring

Quick Identifier

• Topic: sliding-window
• Pattern: Need/Have Variable Window
• Hint: Use two hash maps (need and have) plus a formed counter to track when the window satisfies all character requirements.
• Difficulty: Hard
• Companies: Google, Amazon, Meta, Microsoft, Uber
• LeetCode: 76

Quick Sights

• Time Complexity: O(n + m) where n = length of source, m = length of target.
• Space Complexity: O(|Σ|) – a constant‑size map for the character set (26 for lowercase, 128 for ASCII, etc.).
• Core Mechanism: Expand the right pointer, update have. When formed == required, shrink from the left while maintaining validity, recording the smallest window.

Concept Explanation

Think of the need map as a shopping list of characters you must collect, and have as the basket you carry while walking through the store (source).

1. Expansion – as you move right, you add items to the basket. When an item count hits the exact requirement, you tick one box (formed++).
2. Validity Trigger – when all boxes are ticked (formed == required), you have a complete basket.
3. Contraction – now shrink the left side, trying to discard unnecessary items while keeping the basket complete. The moment you lose a required item, the window becomes invalid and you resume expanding.

Diagram

Study Pattern (SDE3+)

• 0‑3 min: Explain the Need/Have mental model, emphasising the formed counter for O(1) validity checks.
• Implementation pass: Walk through the two‑pointer loop, stressing careful updates of formed only when a character count exactly matches the requirement.
• 5 min extension: Discuss handling Unicode or streaming inputs where the alphabet size is unbounded, requiring a dynamic hashmap and extra space considerations.

Approaches

• Brute force – enumerate all substrings and check frequencies – O(n^2 * |Σ|).
• Optimised sliding window – maintain maps and a formed counter – O(n + m) time, O(|Σ|) space. (Always pick this)

Optimal Solution

Go

func minWindow(source, target string) string {
    if len(target) == 0 || len(source) == 0 {
        return ""
    }
    // Build need map
    need := make(map[byte]int)
    for i := 0; i < len(target); i++ {
        need[target[i]]++
    }
    required := len(need)
    formed := 0
    have := make(map[byte]int)
    left, right := 0, 0
    bestLen := len(source) + 1
    bestStart := 0

    for right < len(source) {
        c := source[right]
        have[c]++
        if need[c] > 0 && have[c] == need[c] {
            formed++
        }
        // Try to contract while window is valid
        for formed == required && left <= right {
            if (right - left + 1) < bestLen {
                bestLen = right - left + 1
                bestStart = left
            }
            lc := source[left]
            have[lc]--
            if need[lc] > 0 && have[lc] < need[lc] {
                formed--
            }
            left++
        }
        right++
    }
    if bestLen > len(source) {
        return ""
    }
    return source[bestStart : bestStart+bestLen]
}

JavaScript

function minWindow(source, target) {
    if (!target.length || !source.length) return "";
    const need = new Map();
    for (const ch of target) need.set(ch, (need.get(ch) || 0) + 1);
    const required = need.size;
    let formed = 0;
    const have = new Map();
    let left = 0, right = 0;
    let best = { len: Infinity, start: 0 };
    while (right < source.length) {
        const c = source[right];
        have.set(c, (have.get(c) || 0) + 1);
        if (need.has(c) && have.get(c) === need.get(c)) formed++;
        while (formed === required) {
            if (right - left + 1 < best.len) {
                best = { len: right - left + 1, start: left };
            }
            const lc = source[left];
            have.set(lc, have.get(lc) - 1);
            if (need.has(lc) && have.get(lc) < need.get(lc)) formed--;
            left++;
        }
        right++;
    }
    return best.len === Infinity ? "" : source.slice(best.start, best.start + best.len);
}

Walkthrough

Input: source = "ADOBECODEBANC", target = "ABC"

• Expand until we have A,B,C → window [0,5] (ADOBEC). Record length 6.
• Shrink left, drop A → window invalid, resume expanding.
• Continue until we hit window [9,12] (BANC). Record length 4, which is minimal.
• Return "BANC".

Edge Cases

• Target longer than source → return "".
• Target empty → return "" (clarify with interviewer).
• Multiple occurrences of a character in target – handled via counts in need.

Pitfalls

• Using the length of the target instead of the number of distinct characters for required.
• Forgetting to decrement formed only when a required character count drops below its need.
• Not handling the case where no valid window exists (should return empty string).

Similar Problems

• [3. Longest Substring Without Repeating Characters] – variable window with distinct char count.
• [567. Permutation in String] – fixed‑size window with need/have.
• [239. Sliding Window Maximum] – different pattern (monotonic deque).

Mind‑Map Tags

#sliding-window #need-have #variable-window #hashmap #hard