76. Minimum Window Substring

Q: Why 'formed' instead of comparing maps?

Comparing maps on every right-pointer step is O(charset). The formed counter increments/decrements in O(1) per step, keeping the whole algorithm O(m + n).

Q: What if t has chars not in s at all?

Then formed never reaches required and bestLen stays Infinity — we return the empty string, as required.

hardAsked at Uber

Find the smallest substring of s that contains every char of t (with multiplicities). Uber asks this as the canonical 'two-pointer plus need/have' sliding-window template — they want to see the formed-count trick.

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

Source citations

Public interview reports confirming this problem appears in Uber loops.

Glassdoor (2026-Q1)— Uber L4/L5 onsite reports include this as a frequent sliding-window hard.
Blind (2025-12)— Recurring in Uber senior interview reports as the harder follow-up after a sliding-window medium.

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.

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: Smallest window containing A, B, and C.

Example 2

Input

s = "a", t = "a"

Output

"a"

Example 3

Input

s = "a", t = "aa"

Output

""

Explanation: Two 'a's needed, only one available.

Approaches

1. Brute-force enumerate windows

For every (i, j), check whether the substring s[i..j] covers t.

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

function minWindowBrute(s, t) {
  function covers(sub, t) {
    const need = new Map();
    for (const c of t) need.set(c, (need.get(c) || 0) + 1);
    for (const c of sub) {
      if (need.has(c)) {
        need.set(c, need.get(c) - 1);
        if (need.get(c) === 0) need.delete(c);
      }
    }
    return need.size === 0;
  }
  let best = '';
  for (let i = 0; i < s.length; i++) {
    for (let j = i + t.length; j <= s.length; j++) {
      const sub = s.slice(i, j);
      if (covers(sub, t) && (!best || sub.length < best.length)) best = sub;
    }
  }
  return best;
}

Tradeoff: Cubic. Useful to articulate the brute-force before the linear template.

2. Sliding window with need/have counter (optimal)

Expand right pointer until window covers t (have == need). Then shrink from left while still valid. Track best.

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

function minWindow(s, t) {
  if (t.length > s.length) return '';
  const need = new Map();
  for (const c of t) need.set(c, (need.get(c) || 0) + 1);
  const have = new Map();
  let formed = 0;
  const required = need.size;
  let l = 0, bestLen = Infinity, bestL = 0;
  for (let r = 0; r < s.length; r++) {
    const c = s[r];
    have.set(c, (have.get(c) || 0) + 1);
    if (need.has(c) && have.get(c) === need.get(c)) formed++;
    while (formed === required) {
      if (r - l + 1 < bestLen) { bestLen = r - l + 1; bestL = l; }
      const lc = s[l];
      have.set(lc, have.get(lc) - 1);
      if (need.has(lc) && have.get(lc) < need.get(lc)) formed--;
      l++;
    }
  }
  return bestLen === Infinity ? '' : s.slice(bestL, bestL + bestLen);
}

Tradeoff: Each char enters and leaves the window at most once, so the total work is O(m + n). The 'formed' counter is what avoids re-scanning the need map on every step.

Uber-specific tips

Uber interviewers grade you on the 'formed counter' optimization specifically. Say: 'I track how many distinct characters have hit their required count. Only when that equals the number of distinct chars in t do I try to shrink left.' Without the counter, you re-scan need on every step and it's effectively O(n*charset).

Common mistakes

Re-checking the entire need map on every right-pointer move (O(n*charset)).
Decrementing 'formed' before the count actually drops below required.
Forgetting that t can have duplicates — need is a multi-set, not a set.

Follow-up questions

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

Permutation in string (LC 567) — same template, smaller window.
Find all anagrams in a string (LC 438) — fixed window size.
Minimum window subsequence (LC 727) — different problem, DP needed.

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 'formed' instead of comparing maps?

Comparing maps on every right-pointer step is O(charset). The formed counter increments/decrements in O(1) per step, keeping the whole algorithm O(m + n).

What if t has chars not in s at all?

Then formed never reaches required and bestLen stays Infinity — we return the empty string, as required.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →