NeetCode #120LC-438MediumArrays & Hashing
← Back to All Problems#120 · #438 · Find All Anagrams in a String(找到字符串中所有字母异位词)
📌 Problem Statement & Constraints
Given two strings
s and p, return all start indices of p's anagrams in s. Constraints: 1 <= s.length, p.length <= 3 * 10^4, lowercase letters.💡 Core Algorithmic Approaches
- A fixed-length sliding window of size
len(p)is the natural structure, since an anagram must match the length. - Maintain a character-count map for the window and compare it with the count map of
p. - Slide the window one step at a time: add the entering character, remove the leaving character.
- Comparing two count maps is O(26) here, so the total cost is O(26n) = O(n) with a small constant.
💻 Benchmark Python3 Implementation
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
from collections import Counter
need = Counter(p)
k = len(p)
if len(s) < k:
return []
window = Counter(s[:k])
res = [0] if window == need else []
for i in range(k, len(s)):
window[s[i]] += 1 # entering character
left = s[i - k]
window[left] -= 1 # leaving character
if window[left] == 0:
del window[left] # keep the maps comparable
if window == need:
res.append(i - k + 1)
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n) with a constant factor of the alphabet size for the map comparison, so O(26n).
💾 Space Complexity
O(1) beyond the output, since the counters hold at most 26 entries.
⚠️ Interview Pitfalls & Follow-ups
- Forgetting to delete zero-count keys:
Counter({'a': 0}) != Counter({}), so the equality test would fail spuriously. This is the most common bug in this problem. - Rebuilding the window counter each step: O(n * k) instead of O(n).
- Only comparing the sums of the counts: equal sums do not imply equal multisets.
- Missing the first window: the initial window must be checked before the slide loop starts.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.