24. Minimum Window Substring

hardAsked at Indeed

Find the smallest window in string s containing all characters of string t — Indeed applies this sliding-window pattern to relevance window extraction in resume-to-job-description matching.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-20

Problem

Given two strings s and t of lengths m and n, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. Return an empty string if no such window exists.

Constraints

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"

Approaches

1. Brute force

Check every substring of s and test if it contains all characters of t.

Time: O(m^2 * n)
Space: O(m + n)

// O(m^2) substrings, each checked in O(n) — too slow for large inputs
// Included only as baseline contrast for the interviewer

Tradeoff:

2. Sliding window with frequency maps

Expand the right pointer until the window satisfies t, then shrink from the left to minimize it; track a 'formed' counter to avoid re-scanning the map on every step.

Time: O(m + n)
Space: O(m + n)

function minWindow(s, t) {
  if (!t.length) return '';
  const need = new Map();
  for (const c of t) need.set(c, (need.get(c)||0)+1);
  const window = new Map();
  let have = 0, required = need.size;
  let best = '', left = 0;
  for (let right = 0; right < s.length; right++) {
    const c = s[right];
    window.set(c, (window.get(c)||0)+1);
    if (need.has(c) && window.get(c)===need.get(c)) have++;
    while (have === required) {
      const sub = s.slice(left, right+1);
      if (!best || sub.length < best.length) best = sub;
      const lc = s[left++];
      window.set(lc, window.get(lc)-1);
      if (need.has(lc) && window.get(lc)<need.get(lc)) have--;
    }
  }
  return best;
}

Tradeoff:

Indeed-specific tips

Indeed grades heavily on the 'formed' counter optimization — candidates who track a running count instead of checking the entire map on every window step stand out in search-team interviews.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →