You are given two strings s and t. Return the shortest substring of s that contains every
character of t, repeats included: if t has two as, the substring needs at least two as.
The characters can come in any order, and the substring may hold other characters as well.
If no substring of s works, return the empty string "". If several shortest substrings work,
return the one that starts first (the leftmost).
Example 1
- Input
- s = "XAYBZACB", t = "ABC"
- Output
- "ACB"
ACB (positions 5 to 7) holds an A, a B and a C, and no shorter stretch does.Example 2
- Input
- s = "baab", t = "ab"
- Output
- "ba"
ba and ab both work and are equally short; ba starts first.Example 3
- Input
- s = "a", t = "aa"
- Output
- ""
t needs two as, but s has only one.Constraints
sandteach hold 1 to 10⁵ characters.- Both contain only English letters; upper and lower case are different characters.
Show the pattern
Sliding window
You want the shortest contiguous stretch that satisfies a rule (it holds all of `t`). Grow a window until it does, then shrink it from the left for as long as it still does.
See sliding window in a visualiserShow the approach
Count the characters t needs in a hash map need, and keep missing, how many characters
(repeats included) the window still lacks, starting at the length of t. Move right along s.
If need[s[right]] > 0, that character was missing, so missing drops by one. Decrease
need[s[right]] either way; a negative count means the window has spares of that character.
Whenever missing is 0, the window holds all of t. Shrink it: while the leftmost character is
a spare (its need is negative), give it back and move left on. Now [left, right] is the
shortest valid window ending at right; keep it if it is strictly shorter than the best so far
(strictly, so the leftmost of equal lengths wins). Then give up s[left] too, which makes the
window incomplete again, and carry on to the right.
Time: O(|s| + |t|) · Space: O(k) for k different characters