Shortest Window Covering All Letters
Problem statement
You are given two strings s and t. Find the shortest stretch of consecutive characters of s that contains every letter of t, counting repeats: if t has a letter twice, the stretch needs it at least twice.
- If several shortest stretches exist, return the one that starts furthest to the left.
- If no stretch works, return the empty string
"".
Function
smallestCoveringWindow(s: String, t: String) → StringExamples
Example 1
s = "xyyzyzyx"t = "xyz"return = "zyx"The shortest stretches holding an x, a y and a z have length 3. Checking from the left, the first one is "zyx" at the end (indexes 5 to 7); every earlier stretch of length 3 misses at least one of the three letters (for example "xyy" has no z, and "yyz" has no x).
Example 2
s = "bAaAb"t = "AA"return = "AaA"t needs two uppercase As. The lowercase a does not count, so the shortest stretch is "AaA" (indexes 1 to 3).
Example 3
s = "abc"t = "d"return = ""No stretch of s holds a d, so the answer is the empty string.
Constraints
1 <= s.length, t.length <= 10^4sandtcontain only English letters (uppercase and lowercase are different letters).