Skip to main content

96. Minimum Window Substring

hardAsked at Salesforce

Find the smallest substring containing all characters of a target string. Salesforce uses this as the canonical hard sliding-window problem.

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

Source citations

Public interview reports confirming this problem appears in Salesforce loops.

  • Glassdoor (2026-Q1)— Salesforce uses this pattern in their multi-keyword document matching.
  • Blind (2025-12)— Common Salesforce L5+ onsite question.

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"

Example 2

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

Example 3

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

Approaches

1. Brute force all substrings

Check every substring; verify it contains t.

Time
O(m^2 * n)
Space
O(n)
// TLE.

Tradeoff: Salesforce will fail.

2. Sliding window with frequency match counter

Maintain target count map. Expand right; when window contains t, contract left. Track minimum.

Time
O(m + n)
Space
O(n)
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);
  let have = 0, required = need.size;
  const have_count = new Map();
  let l = 0, bestLen = Infinity, bestStart = 0;
  for (let r = 0; r < s.length; r++) {
    const c = s[r];
    have_count.set(c, (have_count.get(c) || 0) + 1);
    if (need.has(c) && have_count.get(c) === need.get(c)) have++;
    while (have === required) {
      if (r - l + 1 < bestLen) { bestLen = r - l + 1; bestStart = l; }
      const lc = s[l];
      have_count.set(lc, have_count.get(lc) - 1);
      if (need.has(lc) && have_count.get(lc) < need.get(lc)) have--;
      l++;
    }
  }
  return bestLen === Infinity ? '' : s.slice(bestStart, bestStart + bestLen);
}

Tradeoff: Single pass with frequency-match counter (have vs required). Salesforce's preferred answer.

Salesforce-specific tips

Salesforce uses this pattern in their multi-keyword document matching (find the smallest snippet containing all search terms). They specifically grade on the 'have/required' counter trick — counting how many DISTINCT characters have met their required count, not just total chars. Bonus signal: discuss the array-based optimization for ASCII (256-element array instead of Map).

Common mistakes

  • Comparing total character counts instead of per-character — fails on cases like 'AAB' inside 'AABBC' where total doesn't match.
  • Using only `have === required` without the increment-only-on-equality trick — misses the right time to expand.
  • Off-by-one on the slice (end index is exclusive).

Follow-up questions

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

  • Sliding Window Maximum (LC 239).
  • Longest Substring with At Most K Distinct (LC 340).
  • 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 increment have only when have_count === need?

Because we want to track distinct characters that have met their requirement. Going from need-1 to need is the transition; going from need to need+1 is already counted.

Why decrement have only when have_count < need?

Symmetric. Going from need+1 to need keeps the requirement met; only crossing back below counts as 'losing' a satisfied character.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →