Medium · Fixed Frequency Window
Understand → Visualise → Practice.
Return all start indices whose length-pattern substring is an anagram of pattern.
Keep counts for a window as long as the pattern. Moving the window adds one character and removes one, and a match is when the window's counts equal the pattern's.
Build the frequency of each letter in the pattern.
Add the new character on the right and remove the one that falls off the left.
Whenever the counts match, record the window's start.
O(n × alphabet) time, or O(n) by tracking how many letters match, and O(alphabet) space.
Re-counting every window from scratch costs O(n × m).
Read the full guide first: Strings: Frequencies, Matching and Palindromes.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.