Why it works
- missing is the number of letters of t the window still lacks. It changes only when a count crosses 0, so "does the window cover t?" is answered in O(1) instead of comparing counts.
- A letter whose count is below 0 is a spare: dropping it keeps missing at 0. So the window shrinks past spares and letters t does not need, and stops only when it loses a letter it has to have.
- For every right the window is shrunk as far as it still covers t, so the shortest covering window ending at right is measured, and best keeps the shortest of them.
Complexity
Time O(n + m), where n and m are the lengths of s and t: t is counted once, and each letter of s comes into the window once and leaves at most once. Memory O(k) for the counts of k different letters.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗