MediumNeetCode150Hash TableStringSliding Window
Find All Anagrams in a String
Find all start indices of anagram of p in s.
Examples
Input
s = "cbaebabacd", p = "abc"
Output
[0,6]
Anagrams at index 0 ('cba') and 6 ('bac').
Constraints
- •
1 <= s.length, p.length <= 3*10^4
Approaches
Check each window.
CodeT: O(n*k log k) | S: O(k) sorted window
Fixed window with count array.
CodeT: O(n) | S: O(1) 26-char array
def findAnagrams(s, p):
if len(s)<len(p): return []
pc=[0]*26; sc=[0]*26
for i in range(len(p)): pc[ord(p[i])-97]+=1
r=[]
for i in range(len(s)):
sc[ord(s[i])-97]+=1
if i>=len(p): sc[ord(s[i-len(p)])-97]-=1
if sc==pc: r.append(i-len(p)+1)
return rTrack matches for O(1) compare.
CodeT: O(n) | S: O(1)
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Brute Force | O(n*k log k) | O(k) sorted window | Check each window. |
| Sliding Window + Count | O(n) | O(1) 26-char array | Fixed window with count array. |
| Sliding Window Match Count | O(n) | O(1) | Track matches for O(1) compare. |
Brute Force
T: O(n*k log k)S: O(k) sorted window
Check each window.
Sliding Window + Count
T: O(n)S: O(1) 26-char array
Fixed window with count array.
Sliding Window Match Count
T: O(n)S: O(1)
Track matches for O(1) compare.
Common Mistakes
Not handling s shorter than p
Off-by-one in window
Wrong count comparison