Smallest Window Containing All Characters of Another String
Implement smallestWindowContainingAllChars
Given two strings
s and t, return the shortest contiguous substring of s that contains every character of t (including repeats — if t has two 'a's, the window needs at least two). If no such window exists, return an empty string.
Unlike a fixed-size window, this window's size isn't known in advance — it has to grow and shrink as the scan progresses. The sliding windowSliding WindowMaintaining a running result over a contiguous range that grows or shrinks one element at a time, instead of recomputing the result for every range from scratch. technique tracks a frequency count of the window's characters alongside a formed counter — how many of t's distinct characters are currently satisfied. Grow the window right until formed reaches the required count, then greedily shrink from the left — recording the shortest valid window at every step — until a character falls short again. Every character is visited once by each pointer, so the whole scan runs in O(n).
Example 1:
Input: s = "aabec", t = "abc"
Output: "abec"
Example 2:
Input: s = "adobecodebanc", t = "abc"
Output: "banc"
Example 3:
Input: s = "a", t = "a"
Output: "a"
+ 8 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ s.length, t.length ≤ 10⁵ - ●
s and t consist of lowercase English letters only - ●
t.length ≤ s.length
s =
aabec
t =
abc