Why it works
- A permutation of s1 is exactly as long as s1, so only windows of that length can be one, and the window slides one letter at a time over every place it could start.
- need starts as the counts of s1; a letter coming in takes one away, a letter leaving gives one back. Every count is 0 exactly when the window has the same letters as s1, each the same number of times.
- Having the right letters is not enough: "toll" has l, o and t, but one "l" too many and one "o" short. That is why the map keeps counts, not a set.
Complexity
Time O(26 · n), where n is the length of s2: each letter comes in and leaves once, and checking need looks at most at 26 counts. Memory O(1): at most 26 counts.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗