visual walkthrough
Permutation in String
Compare frequency maps incrementally as the window slides.
The idea
A permutation of s1 is any window of s2 with the same length and the same letter counts. Instead of re-counting every window, update the counts as the window slides: one letter enters, one leaves.
Comparing the two small count tables each step is cheap, and the first match answers the question.
Complexity
| approach | time | space |
|---|---|---|
| Sort every window | O(n · m log m) | O(m) |
| Slide with counts | O(n) | O(1) |