Minimum Window Substring
Problem Statement
Given two strings s and t, return the minimum-length substring of s that contains every character of t, including duplicate requirements. If no such substring exists, return an empty string.
Input
Two strings: s, the search text, and t, the multiset of required characters.
Output
The shortest contiguous substring of s that contains all characters from t with the required multiplicities, or an empty string if no such window exists.
Constraints
- •
1 <= s.length, t.length <= 10^5 - •
s and t consist of uppercase and lowercase English letters - •
The answer is unique when it exists
Examples
Example 1
s = ADOBECODEBANC, t = ABC
BANCExample 2
s = a, t = a
aExample 3
s = a, t = aa
Learning Objectives
- Model **t** as required character frequencies rather than a set.
- Track how many distinct required characters are fully satisfied by the current window.
- Use the shortest-valid template: expand until all requirements are met, then shrink to minimize.
- Handle duplicate requirements and irrelevant characters without special cases.
Intuition
Pattern Identification
This is a shortest-valid variable-window problem. A window is valid when it covers the required multiset from t. Expanding right can only add coverage, while shrinking left may remove coverage. That creates the classic two-phase loop: grow until valid, then shrink while still valid to expose the minimum window.
The expand and shrink invariant is based on matched requirements. Maintain need counts from t, window counts from the current substring, and formed, the number of distinct required characters whose window count has reached the needed count. When formed equals the number of required distinct characters, the window is valid and should be minimized immediately.
Common mistakes
- ×Treating **t** as a set and ignoring duplicate characters like **AA**.
- ×Incrementing the matched count every time a required character appears, even after its needed count is already satisfied.
- ×Shrinking before recording the current valid window.
- ×Removing irrelevant characters incorrectly even though they should not affect **formed**.
Algorithm Explanation
Window setup
Build need counts for t using an ASCII table. Track required, the number of distinct characters with positive need. As the window moves over s, update window counts and maintain formed, the number of required characters whose current count is at least exactly satisfied.
Window visualization
For s = ADOBECODEBANC and t = ABC, the window first becomes valid at ADOBEC when it has A, B, and C. Record that length, then shrink from the left. Removing A breaks validity, so expansion resumes. Later, when the window reaches CODEBANC, all requirements are satisfied again. Shrinking removes irrelevant and extra characters until the compact valid window BANC remains. Removing B would break validity, so BANC is the minimum for that right boundary and becomes the final answer.
Algorithm
- Count required characters from t in need and compute required.
- Initialise left = 0, formed = 0, and best window metadata.
- Expand right through s, adding each character to window.
- When a required character count becomes exactly satisfied, increment formed.
- While formed == required, record the current window if it is shorter than the best.
- Remove s[left], decrement formed if that removal makes a required count fall below its need, then increment left.
- Return the best substring if one was recorded; otherwise return an empty string.
Solutions
Solution: Matched frequency sliding window
The window carries two count tables: what is needed from t and what is currently present. A distinct required character contributes to formed only when its count reaches the needed frequency, which handles duplicates naturally.
Step-by-step
- Build the need table and count how many distinct required characters exist.
- Expand the right boundary, updating the current window count.
- When a character reaches its required count, increment formed.
- While all requirements are formed, update the best answer and remove characters from the left.
- If removing a character drops it below its required count, the window becomes invalid and expansion resumes.
- Return the saved best substring, or an empty string if no valid window was found.
O(n + m)
O(1)
Here n is s.length and m is t.length. The two ASCII count tables have fixed size 128.
Java implementation
Dry Run
Sample input
s = ADOBECODEBANC, t = ABC. Track distinct requirements satisfied and the best window after each important expansion or shrink.
| step | right char | left | window state | formed of required | best window |
|---|---|---|---|---|---|
| 1 | A at 0 | 0 | A count satisfied | 1 of 3 | none |
| 2 | B at 3 | 0 | A and B satisfied | 2 of 3 | none |
| 3 | C at 5 | 0 | A, B, C satisfied in ADOBEC | 3 of 3 | ADOBEC |
| 4 | shrink past A | 1 | A no longer satisfied | 2 of 3 | ADOBEC |
| 5 | A at 10 | 1 | all requirements satisfied again in DOBECODEBA | 3 of 3 | ADOBEC |
| 6 | shrink to C | 5 | CODEBA still valid before removing C | 3 of 3 | CODEBA |
| 7 | C at 12 | 6 | ODEBANC valid, then shrink irrelevant chars | 3 of 3 | CODEBA |
| 8 | shrink to BANC | 9 | BANC is valid and length 4 | 3 of 3 | BANC |
The shortest valid window found is BANC. Shrinking stops there because removing B would make the window miss a required character.
Interview Tips
Emphasize that this is a multiset coverage problem, not a set membership problem. The clean explanation is required distinct characters versus formed distinct characters. Record the best window before each left removal, because the window is valid at the top of the shrink loop. Use arrays for ASCII constraints or maps for a larger character set.
Likely follow-ups
- How would the solution change for full Unicode strings?
- How would you return all minimum windows if multiple answers had the same length?
- How would you handle a stream of characters where **s** is not fully stored?
- How would you adapt the approach if each required character had a weight instead of a count?
Similar Problems
Key Takeaways
- Minimum Window Substring is shortest-valid sliding window over required counts.
- Use frequency counts, not sets, because duplicates in **t** matter.
- **formed == required** is the signal to shrink and minimize.
- Record the answer before removing from the left side of a valid window.