Minimum Window Substring
On this page
Problem statement
Given two strings s and t, return the shortest contiguous substring of s that contains every character of t, including repeats. If t has two A's, the window needs at least two A's. If no such window exists, return an empty string.
The hardest of the standard sliding-window problems, and a common "can you keep your invariants straight under pressure" question. The structure is: expand until valid, shrink while valid, and track validity in O(1). Original problem: LeetCode 76.
Example

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Input: s = "a", t = "aa"
Output: "" # s has only one 'a'
Constraints (assumed)
- 1 ≤ |s|, |t| ≤ 100,000.
- Upper- and lowercase English letters.
What this question tests
- The expand–shrink form of the sliding window.
- Tracking "is the window valid?" in O(1) per step instead of comparing whole maps.
- Correct handling of repeated characters in t.
Questions to ask first
- Do repeats in t matter? (Here: yes; "AAB" needs two A's.)
- Case sensitive? (Here: yes.)
- If several shortest windows exist, which one? (Here: any; the code returns the first.)
- Return the window or its length? (Here: the window, so track its start.)
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.