LeetCode #438 Medium

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.

stringsliding-windowhash-table

02

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.

03

Approach

1

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.

2

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.

3

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.

04

Solution & live demo

python

▶1class Solution:
▶2    def findAnagrams(self, s, p):
▶3        from collections import Counter
▶4        k = len(p)
▶5        if k > len(s):
▶6            return []
▶7        need = Counter(p)
▶8        have = Counter()
▶9        matches = 0
▶10        need_keys = len(need)
▶11        res = []
▶12        for r in range(len(s)):
▶13            ch = s[r]
▶14            have[ch] += 1
▶15            if have[ch] == need.get(ch, 0):
▶16                matches += 1
▶17            if r >= k:
▶18                left_ch = s[r - k]
▶19                if have[left_ch] == need.get(left_ch, 0):
▶20                    matches -= 1
▶21                have[left_ch] -= 1
▶22            if r >= k - 1 and matches == need_keys:
▶23                res.append(r - k + 1)
▶24        return res

05

Edge cases

p longer than s

No window of that width exists, so the results list stays empty; the loop condition naturally prevents any comparison from firing.

Every window in s is an anagram of p (e.g. s='abab', p='ab')

Overlapping windows at consecutive start indices are all recorded since the scan never skips ahead after a match.

p has repeated characters

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.

No anagram of p appears in s

matches never reaches the needed key count for any window, and the function returns an empty list.

06

Complexity

Time

O(n)

Space

O(1)

n is len(s); each character enters and leaves the window once, count maps bounded by the 26-letter alphabet.