Skip to main content

25. Minimum Window Substring

hardAsked at Swiggy

Find the shortest substring of s that contains every character of t (with multiplicities).

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 substring 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. All substring check

Enumerate substrings ordered by length, check if it covers t.

Time
O(n^2 * sigma)
Space
O(sigma)
function covers(sub,t){const c={};for(const ch of t)c[ch]=(c[ch]||0)+1;for(const ch of sub)if(c[ch]!==undefined&&--c[ch]===0)delete c[ch];return Object.keys(c).length===0;}
for (let len=t.length; len<=s.length; len++)
  for (let i=0;i+len<=s.length;i++)
    if (covers(s.slice(i,i+len),t)) return s.slice(i,i+len);
return '';

Tradeoff:

2. Sliding window with need count

Maintain a window with a counter of how many distinct chars of t are still missing. Expand right; once the window covers t, contract left while it still covers, tracking the smallest valid window seen.

Time
O(n)
Space
O(sigma)
function minWindow(s, t) {
  if (!s || !t) return '';
  const need = new Map();
  for (const c of t) need.set(c, (need.get(c) || 0) + 1);
  let have = 0, want = need.size;
  const have_cnt = new Map();
  let bestLen = Infinity, bestL = 0;
  let l = 0;
  for (let r = 0; r < s.length; r++) {
    const c = s[r];
    have_cnt.set(c, (have_cnt.get(c) || 0) + 1);
    if (need.has(c) && have_cnt.get(c) === need.get(c)) have++;
    while (have === want) {
      if (r - l + 1 < bestLen) { bestLen = r - l + 1; bestL = l; }
      const lc = s[l];
      have_cnt.set(lc, have_cnt.get(lc) - 1);
      if (need.has(lc) && have_cnt.get(lc) < need.get(lc)) have--;
      l++;
    }
  }
  return bestLen === Infinity ? '' : s.slice(bestL, bestL + bestLen);
}

Tradeoff:

Swiggy-specific tips

Swiggy uses minimum-window for the senior-loop signal that you can keep two pointers and an invariant straight, exactly the discipline needed for their dispatch-window batching engine.

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

Practice these live with InterviewChamp.AI →