Skip to main content

100. Minimum Window Substring

hardAsked at Vercel

Find the smallest substring of s containing all characters of t. Vercel asks this for the sliding-window-with-counter-map pattern — same shape as their 'find the smallest contiguous region that covers all required edge nodes' optimizer.

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

Source citations

Public interview reports confirming this problem appears in Vercel loops.

  • Glassdoor (2025-Q4)— Vercel platform onsite; sliding window expected.
  • Blind (2026-Q1)— Listed as a Vercel signature hard.

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"

Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

Example 2

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

Example 3

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

Approaches

1. Brute force all substrings

For each (i, j), check if s[i..j] covers t.

Time
O(m^2 * n)
Space
O(n)
// Cubic. Mention to motivate the sliding window.

Tradeoff: Way too slow.

2. Sliding window with required-count tracking (optimal)

Two pointers (left, right). Expand right adding chars; track how many required-counts are satisfied. When all satisfied, contract left while still valid; record min window.

Time
O(m + n)
Space
O(alphabet)
function minWindow(s, t) {
  if (s.length < t.length) return '';
  const need = {};
  for (const c of t) need[c] = (need[c] || 0) + 1;
  let required = Object.keys(need).length;
  let formed = 0;
  const have = {};
  let l = 0;
  let best = [Infinity, 0, 0];
  for (let r = 0; r < s.length; r++) {
    const c = s[r];
    have[c] = (have[c] || 0) + 1;
    if (need[c] && have[c] === need[c]) formed++;
    while (formed === required) {
      if (r - l + 1 < best[0]) best = [r - l + 1, l, r];
      const lc = s[l];
      have[lc]--;
      if (need[lc] && have[lc] < need[lc]) formed--;
      l++;
    }
  }
  return best[0] === Infinity ? '' : s.substring(best[1], best[2] + 1);
}

Tradeoff: O(m+n) total. The `formed === required` tracking avoids re-checking the whole have map each iteration — that's the O(1) per-step amortization.

Vercel-specific tips

Vercel grades the formed-counter optimization. Bonus signal: explaining WHY incrementing `formed` only when have[c] EXACTLY equals need[c] (not >=) — once satisfied, additional copies don't change satisfaction. Same logic on the decrement side: only decrement formed when dropping below.

Common mistakes

  • Re-checking the whole have map each step — O(m * alphabet) instead of O(m).
  • Using `>=` on the formed check — counts the same character multiple times.
  • Forgetting the `if (need[c])` guard — pollutes formed with non-required characters.

Follow-up questions

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

  • Permutation in String (LC 567) — fixed-window variant.
  • Find All Anagrams (LC 438) — same shape.
  • Substring with concatenation of all words (LC 30, hard).

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 tracking?

Re-checking the whole have map per character would be O(alphabet) per step, giving O(m * alphabet). The formed counter advances by at most need.size in total, so increments are O(m) amortized.

Why `have[c] === need[c]` and not `>=`?

We want to count this as 'newly satisfied' exactly once — the moment have crosses from need-1 to need. Subsequent extra copies don't add to formed.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →