Sliding Window — Interview Preparation¶

Table of Contents¶

1. Junior Questions
2. Middle Questions
3. Senior Questions
4. Coding Challenge — Minimum Window Substring

Junior Questions¶

Middle Questions¶

Senior Questions¶

Coding Challenge — Minimum Window Substring¶

Problem. Given two strings s and t, return the smallest substring of s that contains every character of t (including multiplicities). Return "" if no such substring exists.

Example. s = "ADOBECODEBANC", t = "ABC" → "BANC".

Constraints. - 1 <= |s|, |t| <= 10^5. - Both strings consist of printable ASCII characters.

Approach. Variable-size sliding window. Maintain need = Counter(t), have = current window counts, matched = number of distinct characters whose required count is met. Expand right; once matched == len(need), shrink left while still valid and track the smallest such window. O(|s| + |t|) time, O(alphabet) space.

Go¶

package main

import (
    "fmt"
    "math"
)

func minWindow(s, t string) string {
    if len(s) < len(t) || len(t) == 0 {
        return ""
    }

    need := make(map[byte]int)
    for i := 0; i < len(t); i++ {
        need[t[i]]++
    }
    required := len(need)

    have := make(map[byte]int)
    matched := 0

    bestLen := math.MaxInt
    bestL := 0
    l := 0

    for r := 0; r < len(s); r++ {
        c := s[r]
        have[c]++
        if need[c] > 0 && have[c] == need[c] {
            matched++
        }

        for matched == required {
            if r-l+1 < bestLen {
                bestLen = r - l + 1
                bestL = l
            }
            left := s[l]
            have[left]--
            if need[left] > 0 && have[left] < need[left] {
                matched--
            }
            l++
        }
    }

    if bestLen == math.MaxInt {
        return ""
    }
    return s[bestL : bestL+bestLen]
}

func main() {
    fmt.Println(minWindow("ADOBECODEBANC", "ABC")) // BANC
    fmt.Println(minWindow("a", "a"))               // a
    fmt.Println(minWindow("a", "aa"))              // ""
}

Java¶

import java.util.HashMap;
import java.util.Map;

public class Solution {

    public static String minWindow(String s, String t) {
        if (s.length() < t.length() || t.isEmpty()) return "";

        Map<Character, Integer> need = new HashMap<>();
        for (char c : t.toCharArray()) {
            need.merge(c, 1, Integer::sum);
        }
        int required = need.size();

        Map<Character, Integer> have = new HashMap<>();
        int matched = 0;

        int bestLen = Integer.MAX_VALUE;
        int bestL = 0;
        int l = 0;

        for (int r = 0; r < s.length(); r++) {
            char c = s.charAt(r);
            have.merge(c, 1, Integer::sum);
            if (need.containsKey(c)
                && have.get(c).intValue() == need.get(c).intValue()) {
                matched++;
            }

            while (matched == required) {
                if (r - l + 1 < bestLen) {
                    bestLen = r - l + 1;
                    bestL = l;
                }
                char left = s.charAt(l);
                have.merge(left, -1, Integer::sum);
                if (need.containsKey(left)
                    && have.get(left) < need.get(left)) {
                    matched--;
                }
                l++;
            }
        }
        return bestLen == Integer.MAX_VALUE
            ? ""
            : s.substring(bestL, bestL + bestLen);
    }

    public static void main(String[] args) {
        System.out.println(minWindow("ADOBECODEBANC", "ABC")); // BANC
        System.out.println(minWindow("a", "a"));               // a
        System.out.println(minWindow("a", "aa"));              // (empty)
    }
}

Python¶

from collections import Counter


def min_window(s: str, t: str) -> str:
    """Smallest substring of s containing every char of t (with multiplicity)."""
    if len(s) < len(t) or not t:
        return ""

    need = Counter(t)
    have: Counter = Counter()
    required = len(need)
    matched = 0

    best_len = float("inf")
    best_l = 0
    l = 0

    for r, c in enumerate(s):
        have[c] += 1
        if c in need and have[c] == need[c]:
            matched += 1

        while matched == required:
            if r - l + 1 < best_len:
                best_len = r - l + 1
                best_l = l
            left = s[l]
            have[left] -= 1
            if left in need and have[left] < need[left]:
                matched -= 1
            l += 1

    return "" if best_len == float("inf") else s[best_l:best_l + best_len]


if __name__ == "__main__":
    print(min_window("ADOBECODEBANC", "ABC"))  # BANC
    print(min_window("a", "a"))                # a
    print(min_window("a", "aa"))               # ""

Discussion points the interviewer will probe¶

• Complexity. Time O(|s| + |t|) — each pointer moves at most |s| times, all map ops are O(1) average. Space O(|s| + |t|) worst case for the maps; O(alphabet) if you use fixed-size arrays.
• Why matched? Comparing the entire have map to need on every step would cost O(alphabet). Tracking matched makes the check O(1).
• Why int[128] over hash map? For ASCII the alphabet is tiny — direct array indexing is faster and avoids allocator pressure in hot loops. Show both, mention the optimization.
• Edge cases. Empty t, t longer than s, t with duplicates ("aabbc"), s == t, no valid window. Test each.
• Follow-ups the interviewer will ask.
• "What if you can't use extra memory?" → Hard with multiplicity; without multiplicity a 26-bit mask works.
• "Stream version: characters arrive one at a time?" → Same algorithm; emit best so far on demand.
• "What if you need ALL minimum windows, not just one?" → Track length; collect every window of that length.
• "Parallelize across chunks?" → Hard (sequential dependence). Chunk + boundary fixup of width |t|.