Find All Anagrams in a String
Given two strings s and p, return the start indices of all occurrences of p's anagrams in s.
Open on LeetCode ↗Intuition
This is the same fixed-window counting trick as Permutation in String, but two things trip people up here that didn't matter before. First, the problem wants the START INDEX of each matching window, not the window's characters -- if you record the substring itself, you throw away exactly the piece of information the answer needs. Second, it wants EVERY occurrence, including overlapping ones: once a window matches, you don't stop or skip ahead, you just record the index and keep sliding one character at a time, because the very next window (starting one position later) can also be a valid anagram. Keep the same fixed-width window with running counts and a matches counter from Permutation in String, and the only change is what happens on a hit: append the left edge's index to the results list instead of returning immediately.
The same fixed-width window as Permutation in String, collecting every match instead of returning on the first. The starting index is r - k + 1, since r is the window's right edge.
Approach
Reuse the fixed-window count/matches machinery
Build a need count map from p, then slide a window of width len(p) across s, updating a have map and a matches counter incrementally exactly as in the permutation-in-string pattern -- one character enters, one leaves, per step.
Record the start index, not the window
Whenever matches equals the number of needed keys, the current window (from r - len(p) + 1 to r) is an anagram of p. Append r - len(p) + 1, the window's left edge, to the results list.
Keep sliding after a hit -- never stop or jump
Do not break out of the loop or advance the window by more than one position after a match. Overlapping windows are both valid independently, so the scan must continue exactly as it would after a miss.
Solution & live demo
Common pitfalls
Recording the right index instead of the left
res.append(r)
res.append(r - k + 1)
The answer is the anagram's starting position. Reporting the right edge shifts every index by k - 1, which looks plausible until compared against expected output.
Rebuilding the counter for each window
for i in range(len(s) - k + 1):
if Counter(s[i:i+k]) == need: res.append(i)have[ch] += 1 ... have[left_ch] -= 1
Slicing and counting per position is O(nk). The sliding window adds one character and removes one, so each step is constant regardless of k.
Not guarding against p being longer than s
need = Counter(p) for r in range(len(s)):
if k > len(s):
return []The window can never reach full width, so r >= k - 1 is never true and the loop runs pointlessly — and any index arithmetic on r - k would be negative. Returning early is both correct and clearer.
Edge cases
No window of that width exists, so the results list stays empty; the loop condition naturally prevents any comparison from firing.
Overlapping windows at consecutive start indices are all recorded since the scan never skips ahead after a match.
The need map's counts greater than 1 are handled the same way as unique characters -- matches is keyed on distinct letters reaching their required count, not on total character count.
matches never reaches the needed key count for any window, and the function returns an empty list.