We need to find every position in s where a contiguous substring of length p.length() is an anagram of p. Two strings are anagrams if they contain exactly the same characters with the same frequencies, in any order.

Every substring we check has the same length, the length of p. The window size never changes, which makes this a fixed-size sliding window problem. The work that matters is checking whether the current window is an anagram of p cheaply, without recomputing everything at each position.

Key Constraints:

Intuition

To check whether two strings are anagrams, sort them both and compare the sorted versions. If the characters match exactly, the strings are anagrams. So for every substring of s whose length equals p, extract it, sort it, and compare it against the sorted version of p.

This works, but sorting each substring from scratch is the expensive part.

Algorithm

Example Walkthrough

Take s = "cbaebabacd", p = "abc". Sorting p gives sortedP = "abc". The window length is 3, so i runs from 0 to 7.

Two windows sort to "abc", at indices 0 and 6, so the answer is [0, 6].

Code

The bottleneck is sorting every substring from scratch. Each window overlaps the previous one by k - 1 characters, yet we discard all of that and re-sort. The next approach replaces sorting with frequency counts that update incrementally as the window slides.

Intuition

Instead of sorting, represent each string by its character frequency count. Two strings are anagrams if and only if their frequency counts are identical. Build a frequency array for p once, then slide a fixed-size window across s while maintaining a frequency array for the current window. When the window slides right by one position, add the entering character and remove the leaving character, then compare the two arrays.

The comparison takes O(26) = O(1) time because there are only 26 lowercase letters, so the whole sweep avoids re-sorting at every step.

Algorithm

Example Walkthrough

Take s = "cbaebabacd", p = "abc". The target counts are pCount = {a:1, b:1, c:1}, all other letters 0. The first window is "cba" with windowCount = {a:1, b:1, c:1}, which equals pCount, so index 0 is recorded. Each slide adds the entering character and removes the leaving one, then compares the full arrays.

The window at index 0 and the window at index 6 both match pCount, giving [0, 6].

Code

This approach is O(n), but at every window position it compares all 26 entries of the two frequency arrays. The next approach removes that full comparison by tracking how many characters already match and updating that count as the window moves.

Intuition

The frequency comparison in Approach 2 rescans all 26 entries even though the window changed in only one or two places. Maintain a matches counter that tracks how many of the 26 characters currently have the same frequency in both the window and p.

When the window slides, at most two character frequencies change: the one entering and the one leaving. Check only those two characters against their target frequency and adjust matches accordingly. When matches reaches 26, every character frequency lines up and the window is an anagram of p.

Algorithm

Example Walkthrough

Take s = "cbaebabacd", p = "abc". The target is pCount = {a:1, b:1, c:1}. The first window "cba" already has those exact counts, and every other letter sits at 0 = 0, so all 26 characters agree and matches = 26. Index 0 is recorded.

Each slide changes at most two counts. The columns below show the entering character, the leaving character, the resulting matches, and whether the window is an anagram.

At start 1, adding e drops e off its target of 0 (matches--) and removing c drops c below its target of 1 (matches--), so matches falls from 26 to 24. At start 6, adding c restores c to 1 (matches++) and removing a keeps a at 1, its target (matches++), bringing matches back to 26 and recording index 6. The final answer is [0, 6].

Code