Find All Anagrams in a String

LeetCode 438 • Medium • Sliding Window

Input: s = "cbaebabacd", p = "abc" → Output: [0, 6]
Fixed-size window (len p). Freq map of window vs p. When match, add left index.

TimeO(n)single pass

SpaceO(1)26-char maps

Window: 0 Match: — Result: [ ]

Window

Match

Result index

Window

—

Freq

—

Result

[ ]

Speed:

Ready

Press Play. Fixed-size window of len(p). When window freq matches p freq, add left to result. Slide: remove s[left], add s[right+1].

✎ Whiteboard

Size:3

⌨ Type It

Practice until you don't need to look. The green highlights are the nuances to burn into memory.

═══ FIND ALL ANAGRAMS — FIXED WINDOW ═══

PATTERN ▸ Fixed-size window + freq map O(n) · O(1)

① BUILD FREQ MAPS

pFreq = Counter(p)

windowFreq = Counter(s[:len(p)])

② SLIDE WINDOW

for left in range(len(s)-len(p)+1):

if windowFreq == pFreq: result.append(left)

remove s[left], add s[left+len(p)] (if in bounds)

③ RETURN

return result

▼ your implementation ▼

Verify your solution: