Minimum Window Substring — Google Sliding Window Interview Question

Problem Statement#

Given strings s and t, return the minimum length contiguous substring of s that contains every character of t with at least the required frequency. Return an empty string if no such window exists.

Constraints:

• 1 <= s.length, t.length <= 10^5
• s and t consist of uppercase and lowercase English letters
• The answer is unique if it exists
• t may contain duplicate characters

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

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

Why This Problem Matters#

This is LeetCode 76 Minimum Window Substring. It is a Google high-frequency hard and also routinely appears at Meta and Amazon. Interviewers favour it because it tests three distinct skills together — sliding window mechanics, frequency map maintenance, and the optimisation insight to track only how many distinct characters are currently satisfied rather than scanning the map every step.

The Core Insight#

Use two pointers l and r defining the current window s[l..r]. Track two maps — need is the frequency of each character in t, and window is the frequency of each character in the current window.

Add a single integer have that counts how many distinct characters in the window have reached their required count. Increment have only when window[c] becomes exactly equal to need[c] after adding. The answer condition is have == required where required = number of distinct characters in t.

Expand r until the window is valid, then shrink l while it stays valid, updating the best window each shrink step. The trick is that have updates in O(1) — never sweep the map.

Visual Dry Run#

Solution (Optimal)#

from collections import Counter, defaultdict
 
class Solution:
    def minWindow(self, s, t):
        if not t:
            return ""
        need = Counter(t)
        window = defaultdict(int)
        required = len(need)
        have = 0
        l = 0
        best = (float('inf'), 0, 0)
        for r, c in enumerate(s):
            window[c] += 1
            if c in need and window[c] == need[c]:
                have += 1
            while have == required:
                if r - l + 1 < best[0]:
                    best = (r - l + 1, l, r)
                lc = s[l]
                window[lc] -= 1
                if lc in need and window[lc] < need[lc]:
                    have -= 1
                l += 1
        return s[best[1]:best[2] + 1] if best[0] != float('inf') else ""

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

Time: O(n + m) — each character of s enters and leaves the window once Space: O(m) — frequency map keyed by characters present in t

Common Mistakes#

• Comparing the entire frequency map on every step instead of using the have counter
• Updating have with greater-than-or-equal, which double-counts when window exceeds need
• Forgetting that t can have duplicates — using a set instead of a counter
• Returning the wrong substring slice — be careful with inclusive versus exclusive end indices
• Not initialising best to a sentinel that distinguishes "no window" from a real window

Interview Tips#

• Sketch the two pointers and write the invariant — have counts satisfied characters, not total
• State the time complexity explicitly as O(n + m) and explain why each pointer moves only forward
• Walk through one shrink iteration on the whiteboard to convince the interviewer
• Discuss why a fixed-size array sized 128 beats a hashmap when input is ASCII
• Mention edge cases — empty t, t longer than s, t with characters not in s

Follow-up Questions#

• Find the minimum window with at most k distinct characters. (Hint: the variable-window template flips condition)
• Find the longest substring with all unique characters. (Hint: window of unique chars, not need map)
• Stream a long s — return windows incrementally. (Hint: keep the same state, emit on shrink)
• Permutation in string — does a permutation of t exist as substring? (Hint: fixed-size sliding window)
• Generalise to two needs at once. (Hint: track two have counters)

Key Takeaways#

• LeetCode 76 is a Google high-frequency hard problem
• The sliding window template uses two pointers that each move only forward
• A single integer have tracks how many distinct chars are satisfied — avoid map scans
• Use a counter on t so duplicate-character requirements are honoured
• Expand right, shrink left while valid — best window updates inside the shrink loop
• Time complexity is O(n + m), space is O(m)
• The same template solves Permutation in String, Longest Substring with K Distinct, and many others