You get two strings, s and t. Find the shortest unbroken stretch of s that contains every character of t, counting repeats: if t holds p twice, the stretch must hold at least two ps. Other characters may sit in the stretch too, and order does not matter.
Return that stretch. If no stretch of s contains all of t, return the empty string "". Upper- and lower-case letters are different characters.
TOMATOJUI is the first stretch that holds an O, a T and an I, but its front can be trimmed. TOJUI, starting at index 4, holds all three in 5 characters, and nothing shorter does.
t needs two ss and a p. The stretch ssip has exactly that, plus an i.
s has a capital Z but no lower-case z, so no stretch works.
Constraints
1 <= s.length, t.length <= 10⁵s and t are made of upper- and lower-case English letters.s with the same length contains all of t.Use a window with two ends. Push the right end until the window covers all of t, then pull the left end in for as long as it still does. Every shortest window shows up at one of those moments, and each end only moves forward, so the whole scan is linear.
Call a stretch of s good when it holds every character of t, repeats included. Two facts about good stretches make this problem fast.
Time O(|s| + |t|)Space O(1)
The full walkthrough and code are part of Premium