⚡Flashcard Drill➔
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

  1. A fixed-length sliding window of size len(p) is the natural structure, since an anagram must match the length.
  2. Maintain a character-count map for the window and compare it with the count map of p.
  3. Slide the window one step at a time: add the entering character, remove the leaving character.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems