Skip to main content

58. Minimum Window Substring

hardAsked at Plaid

Find the smallest window in a string containing all characters of a pattern. Plaid asks this because finding the smallest time window covering all required transaction-types in a feed (e.g., debit, credit, fee) is the same primitive.

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

Source citations

Public interview reports confirming this problem appears in Plaid loops.

  • Glassdoor (2025)— Plaid SWE III onsite — variant on multi-type window.
  • Blind (2026)— Plaid backend platform OA.

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 every window

Try every (start, end) pair; check if it contains all of t.

Time
O(m^2 * n)
Space
O(n)
// Brute force. Don't ship.

Tradeoff: Cubic. TLE.

2. Sliding window with two pointers and count map

Expand right until all chars of t are matched. Then shrink left while still valid, recording the smallest valid window. Repeat.

Time
O(m + n)
Space
O(n)
function minWindow(s, t) {
  const need = new Map();
  for (const c of t) need.set(c, (need.get(c) || 0) + 1);
  let have = 0, target = need.size;
  let bestLen = Infinity, bestStart = 0;
  const window = new Map();
  let left = 0;
  for (let right = 0; right < s.length; right++) {
    const c = s[right];
    window.set(c, (window.get(c) || 0) + 1);
    if (need.has(c) && window.get(c) === need.get(c)) have++;
    while (have === target) {
      if (right - left + 1 < bestLen) {
        bestLen = right - left + 1;
        bestStart = left;
      }
      const lc = s[left];
      window.set(lc, window.get(lc) - 1);
      if (need.has(lc) && window.get(lc) < need.get(lc)) have--;
      left++;
    }
  }
  return bestLen === Infinity ? '' : s.slice(bestStart, bestStart + bestLen);
}

Tradeoff: Linear time. The 'have == target' tracker avoids comparing maps inside the loop, which would make it O(m * 26).

Plaid-specific tips

Plaid grades this on whether you track distinct-chars-matched as a single counter (have) rather than comparing entire maps. Bonus signal: connect to required-transaction-types window — find the smallest minute range that contains at least one debit, one credit, and one fee, for compliance checks.

Common mistakes

  • Comparing entire maps inside the loop — O(m * 26) instead of O(m).
  • Updating 'have' without checking 'need.has(c)' — false matches.
  • Forgetting to update 'have' down when window count drops below need.

Follow-up questions

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

  • Permutation in string (LC 567) — variable-size window of fixed size.
  • Smallest window covering all required tokens in a log stream.
  • Generalize to multi-key minimum-window.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

What does 'have' track?

The count of distinct characters where window's count meets need's count. When have == target, the window is valid.

Why not just compare maps?

That's O(26) per step (or O(alphabet)). Tracking 'have' lets each map update be O(1).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →