Skip to main content

76. Minimum Window Substring

hardAsked at Airbnb

Find the smallest substring of s that contains every char of t with multiplicities. Airbnb asks this to test the canonical sliding-window template with need/have counts and a 'formed' counter.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Airbnb loops.

  • Glassdoor (2026-Q1)— Airbnb senior+ onsite reports include this as a recurring sliding-window hard.
  • Blind (2025-12)— Recurring in Airbnb backend interview reports.

Problem

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.

Constraints

  • m == s.length
  • n == t.length
  • 1 <= m, n <= 10^5
  • s and t consist of uppercase and lowercase English letters.

Examples

Example 1

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

Example 2

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

Example 3

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

Explanation: Need two 'a's, only one available.

Approaches

1. Brute-force enumerate windows

For every (i, j), check whether s[i..j] covers t.

Time
O(n^2 * m)
Space
O(m + n)
function minWindowBrute(s, t) {
  function covers(sub, t) {
    const need = new Map();
    for (const c of t) need.set(c, (need.get(c) || 0) + 1);
    for (const c of sub) {
      if (need.has(c)) {
        need.set(c, need.get(c) - 1);
        if (need.get(c) === 0) need.delete(c);
      }
    }
    return need.size === 0;
  }
  let best = '';
  for (let i = 0; i < s.length; i++) {
    for (let j = i + t.length; j <= s.length; j++) {
      const sub = s.slice(i, j);
      if (covers(sub, t) && (!best || sub.length < best.length)) best = sub;
    }
  }
  return best;
}

Tradeoff: Cubic. Mention as a baseline before pivoting.

2. Sliding window with need/have counter (optimal)

Expand right until window covers t. Shrink from left while still covering. Track 'formed' = number of distinct chars whose required count is met.

Time
O(m + n)
Space
O(charset)
function minWindow(s, t) {
  if (t.length > s.length) return '';
  const need = new Map();
  for (const c of t) need.set(c, (need.get(c) || 0) + 1);
  const have = new Map();
  let formed = 0;
  const required = need.size;
  let l = 0, bestLen = Infinity, bestL = 0;
  for (let r = 0; r < s.length; r++) {
    const c = s[r];
    have.set(c, (have.get(c) || 0) + 1);
    if (need.has(c) && have.get(c) === need.get(c)) formed++;
    while (formed === required) {
      if (r - l + 1 < bestLen) { bestLen = r - l + 1; bestL = l; }
      const lc = s[l];
      have.set(lc, have.get(lc) - 1);
      if (need.has(lc) && have.get(lc) < need.get(lc)) formed--;
      l++;
    }
  }
  return bestLen === Infinity ? '' : s.slice(bestL, bestL + bestLen);
}

Tradeoff: Each char enters and leaves the window at most once. 'formed' counter avoids re-scanning the need map per step.

Airbnb-specific tips

Airbnb wants the formed-counter optimization. Say: 'I track how many distinct required characters have hit their target count. Only when formed equals the number of distinct chars in t do I shrink from the left.' Without the counter, you'd re-compare maps on every step — same worst-case but worse constants.

Common mistakes

  • Re-scanning the need map on every right-pointer move.
  • Decrementing formed before the count actually drops below required.
  • Forgetting t can have duplicates (need is multi-set).

Follow-up questions

An interviewer at Airbnb may pivot to one of these next:

  • Permutation in String (LC 567) — fixed window.
  • Find All Anagrams in a String (LC 438) — fixed window.
  • Minimum Window Subsequence (LC 727) — different problem, DP.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why 'formed' over map equality?

Map equality is O(charset) per step. The counter is O(1) per step, keeping the whole algorithm linear.

What if t has chars not in s?

formed never reaches required, bestLen stays Infinity, we return ''.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Minimum Window Substring and other Airbnb interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →