Skip to main content

60. Minimum Window Substring

hardAsked at Ola

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

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 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 English letters

Examples

Example 1

Input
s = "ADOBECODEBANC", t = "ABC"
Output
"BANC"

Example 2

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

Approaches

1. Brute substring check

Enumerate every substring of s and check coverage of t.

Time
O(n^2 * m)
Space
O(m)
// quadratic enumeration; too slow at 10^5

Tradeoff:

2. Sliding window

Expand right until the window covers t; shrink left to find the smallest valid window.

Time
O(m + n)
Space
O(n)
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 left = 0, missing = t.length, best = '', bestLen = Infinity;
  for (let right = 0; right < s.length; right++) {
    if ((need.get(s[right]) ?? 0) > 0) missing--;
    need.set(s[right], (need.get(s[right]) ?? 0) - 1);
    while (missing === 0) {
      if (right - left + 1 < bestLen) { bestLen = right - left + 1; best = s.slice(left, right+1); }
      need.set(s[left], need.get(s[left]) + 1);
      if (need.get(s[left]) > 0) missing++;
      left++;
    }
  }
  return best;
}

Tradeoff:

Ola-specific tips

Ola interviewers favor sliding-window mastery; tie it to finding the shortest time window covering a required mix of driver capabilities.

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

Practice these live with InterviewChamp.AI →