76. Minimum Window Substring

hardAsked at GoDaddy

Find the smallest substring of s containing all characters of t — GoDaddy's log-analysis pipeline uses this sliding-window pattern to extract the tightest matching span of request-ID tokens from large access-log streams without a full-text scan.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-26

Problem

Given two strings s and t, return the minimum window substring of s such that every character in t (including duplicates) is included. If no such window exists, 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"

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

Example 2

Input

s = "a", t = "a"

Output

"a"

Example 3

Input

s = "a", t = "aa"

Output

""

Approaches

1. Brute force

Generate all substrings of s and check each one for containment of t's characters.

Time: O(m^2 * n)
Space: O(n)

function minWindow(s, t) {
  function contains(sub, t) {
    const need = new Map();
    for (const ch of t) need.set(ch, (need.get(ch) || 0) + 1);
    for (const ch of sub) {
      if (need.has(ch)) {
        need.set(ch, need.get(ch) - 1);
        if (need.get(ch) === 0) need.delete(ch);
      }
    }
    return need.size === 0;
  }
  let result = '';
  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) && (result === '' || sub.length < result.length)) {
        result = sub;
      }
    }
  }
  return result;
}

Tradeoff:

2. Sliding window with frequency maps

Expand right pointer to satisfy the window; contract left pointer to minimize it; track how many distinct characters are fully satisfied.

Time: O(m + n)
Space: O(m + n)

function minWindow(s, t) {
  if (!s.length || !t.length) return '';
  const need = new Map();
  for (const ch of t) need.set(ch, (need.get(ch) || 0) + 1);
  const required = need.size;
  let formed = 0;
  const windowCounts = new Map();
  let left = 0;
  let minLen = Infinity;
  let minLeft = 0;
  for (let right = 0; right < s.length; right++) {
    const ch = s[right];
    windowCounts.set(ch, (windowCounts.get(ch) || 0) + 1);
    if (need.has(ch) && windowCounts.get(ch) === need.get(ch)) formed++;
    while (formed === required) {
      if (right - left + 1 < minLen) {
        minLen = right - left + 1;
        minLeft = left;
      }
      const lch = s[left];
      windowCounts.set(lch, windowCounts.get(lch) - 1);
      if (need.has(lch) && windowCounts.get(lch) < need.get(lch)) formed--;
      left++;
    }
  }
  return minLen === Infinity ? '' : s.slice(minLeft, minLeft + minLen);
}

Tradeoff:

GoDaddy-specific tips

GoDaddy's hard-round interviews use Minimum Window Substring to verify you can maintain two frequency maps simultaneously and track the 'formed' invariant precisely — the single most common failure is off-by-one on when to decrement 'formed' during the shrink phase. Walk through the invariant before coding.

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

Practice these live with InterviewChamp.AI →