Skip to main content

100. Minimum Window Substring

hardAsked at Reddit

Find the smallest substring of s containing all chars of t. Reddit uses this sliding-window hard problem to test the contract-and-expand pattern — the same shape used when searching for the smallest active vote-window covering a target user-set during fraud audits.

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

Source citations

Public interview reports confirming this problem appears in Reddit loops.

  • Glassdoor (2026-Q1)— Reddit on-site sliding-window hard.
  • Blind (2025-12)— Reported as Reddit trust-and-safety canonical.

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"

Example 2

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

Example 3

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

Approaches

1. Try every window

Iterate every (l, r); check if window contains t.

Time
O(m^2)
Space
O(n)
// Anti-pattern: O(m^2) windows.

Tradeoff: TLE.

2. Sliding window with character counts (optimal)

Maintain count of required chars. Expand right until window covers t; then shrink left to minimize; track best.

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

Tradeoff: Linear. The 'formed === required' check uses unique-character counts, not total counts — a subtle optimization.

Reddit-specific tips

Reddit interviewers want the formed-counter optimization (not just total char count). Bonus signal: explain the invariant — window covers t iff every required char's count meets its target.

Common mistakes

  • Comparing total window length to t.length (allows duplicates incorrectly).
  • Forgetting to handle duplicates in t (each char's required count matters).
  • Off-by-one when extracting the best substring.

Follow-up questions

An interviewer at Reddit may pivot to one of these next:

  • Longest substring with at most K distinct chars (LC 340).
  • Find all anagrams in a string (LC 438).
  • Permutation in string (LC 567).

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why use 'formed' instead of comparing maps?

Comparing maps each iteration is O(alphabet). The 'formed' counter increments/decrements in O(1).

What if t has duplicates?

need[c] counts duplicates. window.get(c) === need.get(c) signals 'this char's requirement is met'.

Practice these live with InterviewChamp.AI

Drill Minimum Window Substring and other Reddit interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →