25. Minimum Window Substring

hardAsked at Freshworks

Find the smallest window containing every required character — Freshworks frames it as finding the shortest ticket-history window covering every required SLA-breach tag.

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

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 substring exists, return the empty string.

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

Output

""

Approaches

1. Brute force

Try every substring of s; for each, count its characters and check it covers t's count map.

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

// nested loops over (i, j); compare per-substring counts against need

Tradeoff:

2. Sliding window with required counter

Build a need-map from t. Expand r until window has every required char (track 'have' = distinct chars at required count). Then contract l, updating the best window, until invariant breaks.

Time: O(m + n)
Space: O(n)

function minWindow(s, t) {
  if (!t) return '';
  const need = new Map(), have = new Map();
  for (const c of t) need.set(c, (need.get(c) || 0) + 1);
  let required = need.size, matched = 0, l = 0;
  let best = [-1, -1], bestLen = Infinity;
  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)) matched++;
    while (matched === required) {
      if (r - l + 1 < bestLen) { bestLen = r - l + 1; best = [l, r]; }
      const lc = s[l];
      have.set(lc, have.get(lc) - 1);
      if (need.has(lc) && have.get(lc) < need.get(lc)) matched--;
      l++;
    }
  }
  return bestLen === Infinity ? '' : s.slice(best[0], best[1] + 1);
}

Tradeoff:

Freshworks-specific tips

Freshworks watches for the 'matched === required' counter — many candidates re-scan the need-map inside the inner loop, which silently turns it into O(m * alphabet).

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

Practice these live with InterviewChamp.AI →