076. Minimum Window Substring

At a Glance

• Topic: Hash Table
• Pattern: Analyze Pattern
• Difficulty: Hard
• LeetCode: 076

Problem Statement

Given two strings s and t of lengths m and n respectively, 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 testcases will be generated such that the answer is unique.

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC" Output: "BANC" Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

Example 2:

Input: s = "a", t = "a" Output: "a" Explanation: The entire string s is the minimum window.

Example 3:

Input: s = "a", t = "aa" Output: "" Explanation: Both 'a's from t must be included in the window. Since the largest window of s only has one 'a', return empty string.

Constraints:

m == s.length
n == t.length
1 <= m, n <= 105
s and t consist of uppercase...

Approach & Solution Steps

• 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 JS Solution

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);
}

Edge Cases & Pitfalls

• Always consider empty or null inputs.
• Watch out for off-by-one index errors.