153. Smallest Covering Window
A librarian is hunting through a long shelf of spine labels, written as the string s, for the shortest stretch of consecutive labels that still contains every label she needs. The needed labels are the letters of t, and a letter that appears twice in t must appear at least twice in the stretch.
Return the shortest contiguous substring of s that contains every character of t with at least its multiplicity in t. If several such substrings share the minimum length, return the one that starts earliest. If no substring qualifies, return the empty string.
Example 1
- Input:
- s = "wxyyzzxw", t = "zyx"
- Output:
- "xyyz"
- Explanation:
No window of length 3 holds all of z, y and x. The first window of length 4 that does is "xyyz" (indices 1 to 4), so that is the answer.
Example 2
- Input:
- s = "bbcabbc", t = "bcc"
- Output:
- "cabbc"
- Explanation:
The window needs one b and two c letters. The two c letters are at indices 2 and 6, so the window must reach from index 2 to 6, giving "cabbc" of length 5, which also holds a b.
Example 3
- Input:
- s = "abc", t = "abcd"
- Output:
- ""
- Explanation:
t is longer than s, so no window can cover it and the answer is the empty string.
Constraints
1 ≤ s.length, t.length ≤ 105
s and t consist of English letters; uppercase and lowercase letters are different characters.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(n + m)
- Space
- O(1)