Skip to main content

25. Minimum Window Substring

hardAsked at Postman

Find the smallest substring of s that contains every character of t with the required multiplicity.

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

Problem

Given strings s and t, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. 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"

Example 2

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

Approaches

1. Enumerate substrings

Try every (i, j) pair and check coverage against t's frequency map.

Time
O(n^2 * alphabet)
Space
O(alphabet)
// nested loops; check t-map coverage for each substring

Tradeoff:

2. Sliding window with counter

Expand right until window covers t; then contract left while still valid; track the best (length, start). Maintain a 'need' counter for matched chars.

Time
O(n)
Space
O(alphabet)
function minWindow(s, t) {
  if (!t) return '';
  const need = new Map();
  for (const c of t) need.set(c, (need.get(c) || 0) + 1);
  let missing = t.length, lo = 0, start = 0, len = Infinity;
  for (let hi = 0; hi < s.length; hi++) {
    const c = s[hi];
    if ((need.get(c) || 0) > 0) missing--;
    need.set(c, (need.get(c) || 0) - 1);
    while (missing === 0) {
      if (hi - lo + 1 < len) { start = lo; len = hi - lo + 1; }
      const l = s[lo];
      need.set(l, need.get(l) + 1);
      if (need.get(l) > 0) missing++;
      lo++;
    }
  }
  return len === Infinity ? '' : s.slice(start, start + len);
}

Tradeoff:

Postman-specific tips

Postman uses min-window logic for matching required headers in a request stream — the missing counter is the same shape as their header-budget validator.

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

Practice these live with InterviewChamp.AI →