Minimum Window Substring
Hard · Sliding Window · String · Hash Table · Sliding Window
Problem
Given strings s and t, return the shortest substring of s that contains every character of t, including repeats. If no such substring exists, return "".
The characters may appear in any order, and the window may contain extras.
Examples
Input: s = "ADOBECODEBANC", t = "ABC" Output: "BANC"
The shortest window holding one A, one B and one C.
Input: s = "a", t = "a" Output: "a"
Input: s = "a", t = "aa" Output: ""
Only one a is available but two are required.
Constraints
- 1 <= len(s), len(t) <= 10^5
- s and t consist of upper and lower case English letters
Approaches
- Check every substring — time O(n² · alphabet), space O(alphabet)
Follow-up
Can you find an algorithm that runs in O(m + n) time?
Related problems
Start free on Cariara · Coding problems · System design studio
