Skip to main content

76. Minimum Window Substring

hardAsked at LinkedIn

Given strings s and t, return the smallest substring of s that contains every character of t (with multiplicity). LinkedIn asks this on senior loops because the canonical sliding-window template is small to write but easy to break on duplicates.

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

Source citations

Public interview reports confirming this problem appears in LinkedIn loops.

  • Glassdoor (2026-Q1)— LinkedIn senior IC onsite reports cite this as the sliding-window hard.
  • Blind (2025-12)— LinkedIn SWE writeups describe the 'have/need counter' pattern as the explicit signal.

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"

Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from t.

Example 2

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

Example 3

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

Explanation: Both 'a's must be included in the window. Since s has only one 'a', return "".

Approaches

1. Brute-force every substring

Try every (i, j) substring of s; check if it contains every character of t with multiplicity; return the shortest valid one.

Time
O(m^2 * n)
Space
O(n)
function minWindowBrute(s, t) {
  const need = {};
  for (const c of t) need[c] = (need[c] || 0) + 1;
  let best = '';
  for (let i = 0; i < s.length; i++) {
    for (let j = i; j < s.length; j++) {
      const sub = s.slice(i, j + 1);
      const have = {};
      for (const c of sub) have[c] = (have[c] || 0) + 1;
      let ok = true;
      for (const c in need) if ((have[c] || 0) < need[c]) { ok = false; break; }
      if (ok && (!best || sub.length < best.length)) best = sub;
    }
  }
  return best;
}

Tradeoff: TLEs at m = 10^5. Mention it only to motivate sliding window.

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

Expand right pointer until all needed chars are covered (have === need keys with sufficient counts); contract left pointer while still valid, tracking the smallest valid window seen.

Time
O(m + n)
Space
O(n)
function minWindow(s, t) {
  if (t.length === 0 || s.length < t.length) return '';
  const need = {};
  for (const c of t) need[c] = (need[c] || 0) + 1;
  const required = Object.keys(need).length;
  const have = {};
  let formed = 0;
  let l = 0, bestLen = Infinity, bestL = 0;
  for (let r = 0; r < s.length; r++) {
    const c = s[r];
    have[c] = (have[c] || 0) + 1;
    if (need[c] !== undefined && have[c] === need[c]) formed++;
    while (formed === required) {
      if (r - l + 1 < bestLen) { bestLen = r - l + 1; bestL = l; }
      const lc = s[l];
      have[lc]--;
      if (need[lc] !== undefined && have[lc] < need[lc]) formed--;
      l++;
    }
  }
  return bestLen === Infinity ? '' : s.slice(bestL, bestL + bestLen);
}

Tradeoff: O(m + n). The trick is the `formed` counter — it tracks how many distinct chars currently have at least their required count. We only contract when formed === required.

LinkedIn-specific tips

LinkedIn interviewers want the 'expand-then-contract' rhythm articulated before code. Say: 'Right pointer grows the window until it's valid; left pointer shrinks while still valid; track the smallest valid window.' Watch the strict `have[c] === need[c]` increment — must use strict equality to avoid double-counting when duplicates arrive. LinkedIn loops also frequently follow up with Find All Anagrams or Permutation in String — be ready.

Common mistakes

  • Comparing `have[c] >= need[c]` instead of `have[c] === need[c]` when updating formed — over-counts on subsequent duplicates.
  • Re-initializing the entire have map on each expansion — destroys the O(1) per-step invariant.
  • Returning the substring before storing both length and start — easy to get the wrong window when ties exist.

Follow-up questions

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

  • Permutation in String (LC 567) — fixed-window variant, easier.
  • Find All Anagrams in a String (LC 438) — return all valid window starts.
  • Smallest Subarrays With Maximum Bitwise OR (LC 2411) — same sliding-window pattern with a different validity predicate.

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 is the `formed` counter needed?

Without it you'd have to compare all entries of have vs need on every iteration — O(alphabet) per step. The counter reduces validity-check to O(1) by tracking only the count of 'satisfied' character types.

How do duplicate characters in t affect the algorithm?

They're handled by the strict equality check. If t = 'aab', need['a'] = 2. When we contract and have['a'] drops from 2 to 1, formed decrements. When we expand back to have['a'] = 2 (NOT 3), formed increments — only at the precise transition.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →