Skip to main content

28. Minimum Window Substring

hardAsked at Instacart

Find the shortest substring containing all required characters — Instacart uses the sliding-window pattern when scanning product descriptions for a mandatory set of nutritional keywords in the shortest possible text span.

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

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 present in the window. If no such window exists, return the empty string "".

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"

Explanation: The minimum window containing A, B, and C is "BANC".

Example 2

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

Approaches

1. Brute force all substrings

Check every substring of s to see if it contains all characters of t; track the shortest.

Time
O(m^2 * n)
Space
O(n)
function minWindow(s, t) {
  const need = new Map();
  for (const c of t) need.set(c, (need.get(c) || 0) + 1);

  let best = '';
  for (let i = 0; i < s.length; i++) {
    const have = new Map();
    for (let j = i; j < s.length; j++) {
      have.set(s[j], (have.get(s[j]) || 0) + 1);
      let valid = true;
      for (const [c, cnt] of need) {
        if ((have.get(c) || 0) < cnt) { valid = false; break; }
      }
      if (valid && (best === '' || j - i + 1 < best.length)) {
        best = s.slice(i, j + 1);
        break;
      }
    }
  }
  return best;
}

Tradeoff:

2. Sliding window with two pointers

Expand the right pointer until the window covers all of t; then contract from the left to minimize window size. Track a 'formed' count of characters satisfied.

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 have = new Map();
  let formed = 0;
  const required = need.size;

  let lo = 0, minLen = Infinity, minLo = 0;

  for (let hi = 0; hi < s.length; hi++) {
    const c = s[hi];
    have.set(c, (have.get(c) || 0) + 1);
    if (need.has(c) && have.get(c) === need.get(c)) formed++;

    while (formed === required) {
      if (hi - lo + 1 < minLen) {
        minLen = hi - lo + 1;
        minLo = lo;
      }
      const lc = s[lo++];
      have.set(lc, have.get(lc) - 1);
      if (need.has(lc) && have.get(lc) < need.get(lc)) formed--;
    }
  }

  return minLen === Infinity ? '' : s.slice(minLo, minLo + minLen);
}

Tradeoff:

Instacart-specific tips

Instacart's content team validates product description coverage against mandatory attribute sets. The sliding-window approach is the gold standard — interviewers will ask you to walk through a hand-trace before coding. Pay attention to the 'formed' counter: it lets you determine window validity in O(1) rather than re-scanning the need map on every step.

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

Practice these live with InterviewChamp.AI →