Skip to main content

76. Minimum Window Substring

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 Sam K., Founder, InterviewChamp.AI · Last verified

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.

More Uber coding interview questions

See all Uber problems →

Companies that also ask Minimum Window Substring