20. Minimum Window Substring

hardAsked at GitHub

Variable sliding window to find the smallest substring containing all target characters — the canonical string-processing hard problem GitHub tests in senior-level loops.

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. Return empty string if no such window exists.

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 = 'a'

Output

'a'

Approaches

1. Brute force: all substrings

Generate all O(n²) substrings, check each contains all t characters, track minimum length.

Time: O(n^2 * |t|)
Space: O(|t|)

// For each (i,j) pair, check if s.slice(i,j) contains all chars of t
// Track shortest valid window — too slow for n=10^5

Tradeoff:

2. Expand-contract sliding window

Use a right pointer to expand the window until all t characters are covered, then contract from the left while still valid, recording the minimum. A `formed` counter avoids comparing full maps each step.

Time: O(|s|+|t|)
Space: O(|s|+|t|)

function minWindow(s, t) {
  const need = {};
  for (const c of t) need[c] = (need[c]||0) + 1;
  let have = 0, required = Object.keys(need).length;
  const window = {};
  let ans = '', l = 0;
  for (let r = 0; r < s.length; r++) {
    const c = s[r];
    window[c] = (window[c]||0) + 1;
    if (need[c] && window[c] === need[c]) have++;
    while (have === required) {
      const candidate = s.slice(l, r+1);
      if (!ans || candidate.length < ans.length) ans = candidate;
      window[s[l]]--;
      if (need[s[l]] && window[s[l]] < need[s[l]]) have--;
      l++;
    }
  }
  return ans;
}

Tradeoff:

GitHub-specific tips

GitHub asks Minimum Window Substring at E5+ levels and expects you to explain the expand-contract invariant before coding; also discuss how you'd handle Unicode multi-byte characters in a real diff-search context.

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

Practice these live with InterviewChamp.AI →