22. Minimum Window Substring

hardAsked at Notion

Find the smallest window in a string that contains all required characters — the core algorithm behind Notion's full-text search highlight, which must locate the tightest snippet covering every query token in a document block.

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

Problem

Given two strings s and t, return the minimum window substring of s that contains all characters of t (including duplicates). If no such window exists, return an empty string.

Constraints

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

Examples

Example 1

Input

s = "ADOBECODEBANC", t = "ABC"

Output

"BANC"

Explanation: Minimum window containing A, B, C is "BANC".

Example 2

Input

s = "a", t = "a"

Output

"a"

Approaches

1. Brute force — all substrings

Generate every substring of s; check each for t's character requirements. O(n^2) substrings, O(m) check each.

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

function minWindow(s, t) {
  function contains(window, need) {
    const freq = new Map();
    for (const c of window) freq.set(c, (freq.get(c) || 0) + 1);
    for (const [c, cnt] of need) {
      if ((freq.get(c) || 0) < cnt) return false;
    }
    return true;
  }
  const need = new Map();
  for (const c of t) need.set(c, (need.get(c) || 0) + 1);
  let result = '';
  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 (contains(sub, need) && (!result || sub.length < result.length)) result = sub;
    }
  }
  return result;
}

Tradeoff:

2. Sliding window with frequency map

Track a 'have' count and a 'need' count; expand right until all required chars are covered, then shrink left to minimize window, recording the best answer each time.

Time: O(|s| + |t|)
Space: O(|s| + |t|)

function minWindow(s, t) {
  if (!s || !t) 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;
  const required = need.size;
  let left = 0;
  let minLen = Infinity;
  let minStart = 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) {
      if (right - left + 1 < minLen) {
        minLen = right - left + 1;
        minStart = left;
      }
      const leftChar = s[left];
      window.set(leftChar, window.get(leftChar) - 1);
      if (need.has(leftChar) && window.get(leftChar) < need.get(leftChar)) have--;
      left++;
    }
  }
  return minLen === Infinity ? '' : s.slice(minStart, minStart + minLen);
}

Tradeoff:

Notion-specific tips

Notion's search highlights the tightest snippet covering all query terms — this is minimum window in disguise. Interviewers want you to articulate the 'have vs required' counter trick: it converts O(|charset|) window-validity checks to O(1). Show you understand why decrementing 'have' only when count drops below the threshold is correct.

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 Notion interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →