Skip to main content

25. Minimum Window Substring

hardAsked at Chegg

Find the smallest substring of s containing all characters of t — a sliding window hard Chegg applies to substring matching in their document search and plagiarism detection pipelines.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given two strings s and t of lengths m and n, 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.

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 = "a"
Output
"a"

Approaches

1. Brute force

Check every substring of s to see if it contains all characters of t — O(m^2 * n).

Time
O(m^2 * n)
Space
O(1)
function minWindow(s, t) {
  let res = '';
  for (let i = 0; i < s.length; i++)
    for (let j = i + 1; j <= s.length; j++) {
      const sub = s.slice(i, j);
      if (contains(sub, t) && (!res || sub.length < res.length)) res = sub;
    }
  return res;
}

Tradeoff:

2. Sliding window with frequency maps

Expand right to include characters, shrink left when all t characters are covered; track the satisfied-character count to avoid re-scanning the entire window on each step.

Time
O(m+n)
Space
O(m+n)
function minWindow(s, t) {
  const need = new Map();
  for (const c of t) need.set(c, (need.get(c) || 0) + 1);
  let have = 0, required = need.size;
  const window = new Map();
  let lo = 0, minLen = Infinity, resLo = 0;
  for (let hi = 0; hi < s.length; hi++) {
    const c = s[hi];
    window.set(c, (window.get(c) || 0) + 1);
    if (need.has(c) && window.get(c) === need.get(c)) have++;
    while (have === required) {
      if (hi - lo + 1 < minLen) { minLen = hi - lo + 1; resLo = lo; }
      const lc = s[lo++];
      window.set(lc, window.get(lc) - 1);
      if (need.has(lc) && window.get(lc) < need.get(lc)) have--;
    }
  }
  return minLen === Infinity ? '' : s.slice(resLo, resLo + minLen);
}

Tradeoff:

Chegg-specific tips

Chegg interviewers focus on the 'have vs required' bookkeeping trick — explain how counting satisfied unique characters avoids iterating over the entire need map inside the inner loop.

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

Practice these live with InterviewChamp.AI →