Skip to main content

29. Minimum Window Substring

mediumAsked at Tripadvisor

Find the shortest substring containing all required characters — Tripadvisor's review-analysis pipeline applies this sliding-window pattern to locate the most concise snippet in a hotel review that covers all required quality keywords for search-result snippets.

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 there is no such substring, return the empty string "". The testcases will be generated such that the answer is unique.

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"

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

Example 2

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

Approaches

1. Brute force all substrings

Check every substring of s; verify if it contains all characters of t using a frequency map. Return the shortest valid one.

Time
O(m^2 * n)
Space
O(n)
function minWindow(s, t) {
  let result = '';
  const need = {};
  for (const c of t) need[c] = (need[c] || 0) + 1;
  function covers(sub) {
    const have = {};
    for (const c of sub) have[c] = (have[c] || 0) + 1;
    for (const [c, cnt] of Object.entries(need)) {
      if ((have[c] || 0) < cnt) return false;
    }
    return true;
  }
  for (let i = 0; i < s.length; i++) {
    for (let j = i + 1; j <= s.length; j++) {
      const sub = s.slice(i, j);
      if (covers(sub) && (result === '' || sub.length < result.length)) result = sub;
    }
  }
  return result;
}

Tradeoff:

2. Sliding window with two pointers (optimal)

Expand right pointer to satisfy all t requirements; once satisfied, shrink left pointer to minimize window. Track 'have' vs 'need' counts to avoid re-scanning the window.

Time
O(m + n)
Space
O(m + n)
function minWindow(s, t) {
  if (!t.length) return '';
  const need = {}, have = {};
  for (const c of t) need[c] = (need[c] || 0) + 1;
  const required = Object.keys(need).length;
  let formed = 0, lo = 0, minLen = Infinity, minStart = 0;
  for (let hi = 0; hi < s.length; hi++) {
    const c = s[hi];
    have[c] = (have[c] || 0) + 1;
    if (need[c] !== undefined && have[c] === need[c]) formed++;
    while (formed === required) {
      if (hi - lo + 1 < minLen) { minLen = hi - lo + 1; minStart = lo; }
      const lc = s[lo];
      have[lc]--;
      if (need[lc] !== undefined && have[lc] < need[lc]) formed--;
      lo++;
    }
  }
  return minLen === Infinity ? '' : s.slice(minStart, minStart + minLen);
}

Tradeoff:

Tripadvisor-specific tips

Tripadvisor's review-snippet generator needs to find the shortest excerpt from a hotel review that covers all 'must-mention' quality attributes — this is the exact problem. Interviewers want to see the two-pointer sliding window with a 'formed' counter rather than re-checking the entire window on every move. The key insight to articulate: only track characters that appear in t, and use the formed == required shortcut to trigger contraction. This reduces the inner loop to amortized O(1) per 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 Tripadvisor interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →