Minimum Window Substring: definition
Find the shortest contiguous part of a text that covers every required character count. Extra characters are allowed; uppercase and lowercase letters are different.
Task example: Minimum Window Substring
Given nonempty English-letter strings s and t, return the shortest substring of s containing all characters of t, including repetitions. Return an empty string if none exists. The original task guarantees a unique answer; this demo keeps the first shortest window when inputs have a tie.
BANC contains A, B, and C in four characters. ADOBEC is valid too, but longer. Unlike an anagram, a valid window may contain extra letters such as N.
Brute force: video explanation
s = "ADOBECODEBANC", t = "ABC" → "BANC"
Prefer reading? Follow the steps below.
- Count t once. For every left index, create fresh counts and extend right until each required count is covered.
- At the first valid window for a start, save its indices if shorter than the best. Then break: extending the same start cannot give a shorter answer.
- The best lengths improve from 6 (ADOBEC) to 5 (EBANC) to 4 (BANC). Copy only the final substring; return "" when no window was found.
Time complexity · O(n² + m)
Let n = len(s), m = len(t). Counting t takes O(m). Across all starts there are O(n²) extensions; each coverage check scans at most 52 English letters. Total: O(n² + m).
Space complexity · O(1) auxiliary + O(k) output
The tables use O(1) auxiliary space for the fixed 52-letter alphabet. Stored indices are constant size. Copying the returned substring uses O(k) output space, where k is its length.
Sliding window: video explanation
s = "ADOBECODEBANC", t = "ABC" → "BANC"
Prefer reading? Follow the steps below.
- Initialize need with the target counts and missing = len(t). When adding ch, reduce missing only if need[ch] > 0, then decrement need[ch]. Negative counts represent surplus letters.
- While missing == 0, record a shorter window and remove s[left]. Restore its need count; if it becomes positive, a required occurrence is missing. Advance left and expand again when necessary.
- ADOBEC first covers ABC. Shrinking loses A, so expand to the next A. Later, the C at index 12 restores coverage; shrinking reaches BANC. Return the saved best substring.
Reusing the window avoids restarting for every left index. Both pointers only move forward, so the shrinking loop does not make the algorithm quadratic.
Time complexity · O(m + n)
Count t in O(m). Each character of s enters once and leaves at most once, giving O(n) total boundary moves. Copying the final answer costs O(k), already bounded by O(n). Total: O(n + m).
Space complexity · O(1) auxiliary + O(k) output
The tables use O(1) auxiliary space for the fixed 52-letter alphabet. Stored indices are constant size. Copying the returned substring uses O(k) output space, where k is its length.