58. Minimum Window Substring
hardAsked at PlaidFind 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 Sam K., 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.lengthn == t.length1 <= m, n <= 10^5s and t consist of uppercase and lowercase English letters.
Examples
Example 1
s = "ADOBECODEBANC", t = "ABC""BANC"Example 2
s = "a", t = "a""a"Example 3
s = "a", t = "aa"""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.
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).