57. Minimum Window Substring

Q: Why need vs have, why not just have <= need?

Both work, but counting 'formed when have matches need' avoids rechecking the whole window. We only update the formed counter at the transition points.

Q: Duplicates in t?

Need uses counts, not just distinct chars. t = 'aab' means 2 a's + 1 b — formed only when have['a'] >= 2 AND have['b'] >= 1.

hardAsked at Workday

Given two strings s and t, find the minimum window in s that contains all characters of t. Workday uses this for sliding-window mastery — same shape as finding the shortest payroll-period window covering all of a multi-state employee's tax jurisdictions.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

Glassdoor (2026-Q1)— Workday SDE2 onsite — hard sliding-window staple.

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. All substrings

Enumerate substrings, check each.

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

// O(m^2) substrings * O(n) check — too slow

Tradeoff: Won't pass.

2. Sliding window with need/have counters

Expand right until all of t's chars are covered. Then contract left to shrink the window. Track best.

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 required = need.size, formed = 0;
  const have = new Map();
  let bestLen = Infinity, bestStart = 0;
  let l = 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; bestStart = l; }
      const left = s[l];
      have.set(left, have.get(left) - 1);
      if (need.has(left) && have.get(left) < need.get(left)) formed--;
      l++;
    }
  }
  return bestLen === Infinity ? '' : s.slice(bestStart, bestStart + bestLen);
}

Tradeoff: O(m + n) time. The required/formed counters let us check 'window valid?' in O(1).

Workday-specific tips

Workday wants you to break this into expand vs contract phases. State 'formed == required' as the validity invariant before coding. The trick: a character in t counts ONLY when its have == need, not while exceeding.

Common mistakes

Incrementing formed every time a needed char appears — should only increment when have catches up to need.
Treating window validity as 'all distinct chars present' — must respect duplicates in t.
Returning bestLen instead of the substring.

Follow-up questions

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

Find All Anagrams in a String (LC 438).
Permutation in String (LC 567).
Longest Substring with At Most K Distinct (LC 340).

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 need vs have, why not just have <= need?

Both work, but counting 'formed when have matches need' avoids rechecking the whole window. We only update the formed counter at the transition points.

Duplicates in t?

Need uses counts, not just distinct chars. t = 'aab' means 2 a's + 1 b — formed only when have['a'] >= 2 AND have['b'] >= 1.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →