Skip to main content

60. Minimum Window Substring

hardAsked at Snowflake

Find the minimum window in s that contains all characters of t. Snowflake asks this to test sliding-window mastery with multi-character constraints — same shape as streaming join-key matching where you maintain a running multiset.

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

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2026-Q1)— Snowflake execution-engine team uses this in onsites to set up streaming-join discussion.
  • LeetCode Discuss (2025-12)— Recurring at Snowflake SDE-I onsites.

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. The testcases will be generated such that the answer is unique.

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
""

Approaches

1. Try every window

For every (i, j), check whether substring s[i..j] contains all of t.

Time
O(m^2 * n)
Space
O(n)
// outline only — cubic, don't ship.

Tradeoff: Way too slow.

2. Sliding window with need counter (optimal)

Maintain need[] from t, current have[] count, and a 'formed' counter (chars satisfying need). Expand right; when formed == required, try to shrink left to minimize.

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 required = need.size;
  let l = 0, formed = 0;
  const have = new Map();
  let best = [-1, 0, 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 (best[0] === -1 || r - l + 1 < best[0]) best = [r - l + 1, l, r];
      const lc = s[l];
      have.set(lc, have.get(lc) - 1);
      if (need.has(lc) && have.get(lc) < need.get(lc)) formed--;
      l++;
    }
  }
  return best[0] === -1 ? '' : s.slice(best[1], best[2] + 1);
}

Tradeoff: Single pass with two pointers. The 'formed' counter avoids re-validating the whole window.

Snowflake-specific tips

Snowflake interviewers want the formed-counter trick — instead of comparing two maps every step, you only update one counter when a character's count exactly matches its need. Bonus signal: pivot to streaming-join state — for a windowed join that requires multiple keys to match, you'd maintain a similar 'formed' count of satisfied key constraints.

Common mistakes

  • Comparing have and need maps every step — O(charset) per step, blowing past linear.
  • Decrementing formed on every left shift instead of only when have falls below need.
  • Off-by-one on the substring extraction (use r - l + 1, not r - l).

Follow-up questions

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

  • Permutation in String (LC 567).
  • Find All Anagrams in a String (LC 438).
  • How does a streaming join maintain partial-match state?

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 a formed counter?

It lets us check window validity in O(1). Without it, we'd compare two maps every step — O(charset) per step.

Why only decrement formed when have < need?

If have was 3 and need was 2, removing one still leaves have == 2 == need — still satisfied. Only decrement when have falls below need.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →