Smallest Covering Window
HardSliding Window
Problem
A search engine highlights the shortest snippet of a document s that contains every character of the query t, including repeats: if t has two as, the snippet needs at least two as.
Return that shortest substring of s. If several have the same minimal length, return the one that starts first. If no substring covers t, return the empty string. Matching is case-sensitive.
Example 1
- Input:
- s = "xaybzcxab", t = "abc"
- Output:
- "cxab"
Covering windows include "aybzc" and "bzcxa" (length 5), but "cxab" needs only 4 characters.
Example 2
- Input:
- s = "aa", t = "aaa"
- Output:
- ""
s has only two a's.
Example 3
- Input:
- s = "A", t = "a"
- Output:
- ""
Constraints
- 1 ≤ s.length, t.length ≤ 10^5
- s and t consist of English letters (upper and lower case).
Hint
Show the first hint
If a window covers t, so does any larger window that contains it. Grow until covered, then shrink.
Walkthrough
How to approach it
01Clarify before coding
- Do repeated characters in t count? Yes, multiplicity matters.
- Case-sensitive? Yes, 'A' does not cover 'a'.
- Ties? Return the leftmost shortest window.
02Brute force
For every start, extend right until the window covers t (checking counts), and keep the shortest.
Cost: O(n²·σ) time with a fresh coverage check, or O(n²) with incremental counts: far too slow for 10^5.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.