LeetCode 438: Find All Anagrams in a String Solution in Python – A Step-by-Step Guide

What Is LeetCode 438: Find All Anagrams in a String?

In LeetCode 438: Find All Anagrams in a String, you’re given two strings: s (the big string) and p (the pattern). Your task is to return a list of all starting indices in s where a substring of length p is an anagram of p—meaning it has the same letters with the same frequencies, just in any order. For example, in "cbaebabacd" with pattern "abc", the anagrams "cba" (index 0) and "bac" (index 6) are your targets. It’s like finding all the hidden word twins in a giant letter soup.

Problem Statement

• Input: s (string)—the larger string; p (string)—the pattern.
• Output: List[int]—starting indices of all anagrams of p in s.
• Rules:
• An anagram is a permutation of p with the same length and letter frequencies.
• Return indices in any order.

Constraints

• 1 <= s.length, p.length <= 3 * 10^4.
• s and p contain only lowercase English letters.

Examples to Kick Things Off

• Input: s = "cbaebabacd", p = "abc"
• Output: [0, 6]
• "cba" (0-2) and "bac" (6-8) are anagrams of "abc".
• Input: s = "abab", p = "ab"
• Output: [0, 1, 2]
• "ab" (0-1), "ba" (1-2), "ab" (2-3) all match "ab".
• Input: s = "aa", p = "aaa"
• Output: [] (No substring of length 3 possible).

Understanding the Problem: Spotting Anagram Twins

To solve LeetCode 438: Find All Anagrams in a String in Python, we need to find all substrings of s with length p that match p’s letter frequencies. A naive check—comparing every substring—would be painfully slow, O(n * m) with sorting or worse. Instead, we’ll use:

• Best Solution (Sliding Window with Frequency Map): O(n) time, O(1) space—fast and scalable.
• Alternative Solution (Brute Force with Sorting): O(n * k log k) time, O(k) space—straightforward but inefficient.

Let’s dive into the sliding window solution—it’s the detective tool we need.

Best Solution: Sliding Window with Character Frequency Map

Why This Is the Best Solution

The sliding window with a frequency map is the top pick because it runs in O(n) time and O(1) space (since the alphabet is fixed at 26 letters), scanning s once while tracking character counts. By sliding a fixed-size window and adjusting frequencies on the fly, we spot anagrams without redundant work. It’s like sliding a magnifying glass over the string, instantly recognizing when the letters align perfectly with the pattern!

How It Works

Here’s the plan:

• Step 1: Build a frequency map for p (e.g., "abc" → {'a':1, 'b':1, 'c':1}).
• Step 2: Initialize a window map for the first len(p) characters of s.
• Step 3: Slide the window across s:
• Remove the leftmost character’s count.
• Add the new rightmost character’s count.
• If the window map matches p’s map, record the start index.
• Step 4: Return all found indices.
• Why It Works:
• Fixed window size (len(p)) ensures we only check valid lengths.
• Frequency maps let us compare in O(1) time per step.

Step-by-Step Example

Example: s = "cbaebabacd", p = "abc"

• Setup:
• p_map: {'a':1, 'b':1, 'c':1}.
• Window size: 3.
• Result: [].
• Initial Window: "cba" (0-2):
• Window_map: {'c':1, 'b':1, 'a':1}.
• Matches p_map, add index 0.
• Slide:
• "bae" (1-3): Remove 'c', add 'e' → {'b':1, 'a':1, 'e':1} (no match).
• "aeb" (2-4): Remove 'b', add 'b' → {'a':1, 'e':1, 'b':1} (no match).
• "eba" (3-5): Remove 'a', add 'a' → {'e':1, 'b':1, 'a':1} (no match).
• "bab" (4-6): Remove 'e', add 'b' → {'b':2, 'a':1} (no match).
• "aba" (5-7): Remove 'b', add 'a' → {'b':1, 'a':2} (no match).
• "bac" (6-8): Remove 'a', add 'c' → {'b':1, 'a':1, 'c':1} (match, add 6).
• "acd" (7-9): Remove 'b', add 'd' → {'a':1, 'c':1, 'd':1} (no match).
• Result: [0, 6].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down for clarity:

Copy codeclass Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        if len(p) > len(s):
            return []

        # Step 1: Frequency map for pattern
        p_map = {}
        for char in p:
            p_map[char] = p_map.get(char, 0) + 1

        # Step 2: Initial window map
        window_map = {}
        for char in s[:len(p)]:
            window_map[char] = window_map.get(char, 0) + 1

        # Step 3: Result list and initial check
        result = [0] if window_map == p_map else []

        # Step 4: Slide the window
        for i in range(len(p), len(s)):
            # Remove leftmost char
            left_char = s[i - len(p)]
            window_map[left_char] -= 1
            if window_map[left_char] == 0:
                del window_map[left_char]

            # Add rightmost char
            right_char = s[i]
            window_map[right_char] = window_map.get(right_char, 0) + 1

            # Check if current window is an anagram
            if window_map == p_map:
                result.append(i - len(p) + 1)

        return result

• Line 3-4: Early exit if p is longer than s.
• Line 7-9: Build p_map (e.g., "abc" → {'a':1, 'b':1, 'c':1}).
• Line 12-14: Build initial window_map for first len(p) chars.
• Line 17: Check first window, add index 0 if match.
• Line 20-29: Slide:
• Line 22-24: Decrease count of left char, remove if 0.
• Line 27-28: Increase count of right char.
• Line 31-32: If maps match, add start index (i - len(p) + 1).
• Time Complexity: O(n)—single pass, O(1) map comparisons.
• Space Complexity: O(1)—maps are bounded by alphabet size (26).

It’s like a word-matching conveyor belt—smooth and fast!

Alternative Solution: Brute Force with Sorting

Why an Alternative Approach?

The brute force method checks every substring of length p by sorting and comparing—O(n * k log k) time, O(k) space (k = len(p)). It’s slower but intuitive, like manually unscrambling each chunk to see if it fits the clue. Great for small cases or learning the basics!

How It Works

• Step 1: For each substring of length p in s:
• Sort it and p.
• If they match, record the start index.
• Step 2: Return all indices.

Step-by-Step Example

Example: s = "cbaebabacd", p = "abc"

• p_sorted: "abc".
• Check:
• "cba" (0-2): "abc" = "abc", add 0.
• "bae" (1-3): "abe" ≠ "abc".
• "aeb" (2-4): "abe" ≠ "abc".
• "eba" (3-5): "abe" ≠ "abc".
• "bab" (4-6): "abb" ≠ "abc".
• "aba" (5-7): "aab" ≠ "abc".
• "bac" (6-8): "abc" = "abc", add 6.
• "acd" (7-9): "acd" ≠ "abc".
• Result: [0, 6].

Code for Brute Force

Copy codeclass Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        if len(p) > len(s):
            return []

        p_sorted = ''.join(sorted(p))
        result = []

        for i in range(len(s) - len(p) + 1):
            window = s[i:i + len(p)]
            if ''.join(sorted(window)) == p_sorted:
                result.append(i)

        return result

• Time Complexity: O(n * k log k)—n windows, sorting k chars.
• Space Complexity: O(k)—sorted strings.

It’s a slow but sure word scramble.

Comparing the Two Solutions

• Sliding Window (Best):
• Pros: O(n), fast, constant space.
• Cons: Slightly trickier.
• Brute Force (Alternative):
• Pros: O(n * k log k), simple.
• Cons: Much slower.

Sliding window wins hands down.

Edge Cases and More Examples

• Input: s = "a", p = "a" → [0].
• Input: s = "ab", p = "c" → [].
• Input: s = "aaa", p = "aa" → [0, 1].

Both handle these cleanly.

Complexity Recap

• Sliding Window: Time O(n), Space O(1).
• Brute Force: Time O(n * k log k), Space O(k).

Sliding window is the champ.

Key Takeaways

• Sliding Window: Efficiency through frequency.
• Brute Force: Simplicity at a cost.
• Python Tip: Dicts are your friends—see [Python Basics](/python/basics).

Final Thoughts: Unscramble the Fun

LeetCode 438: Find All Anagrams in a String in Python is a string-sleuthing delight. The sliding window with a frequency map is your master key, while brute force sorting is a trusty backup. Want more string challenges? Try LeetCode 3: Longest Substring Without Repeating Characters or LeetCode 567: Permutation in String. Ready to find those anagrams? Head to Solve LeetCode 438 on LeetCode and crack the case today—your coding detective skills are ready to shine!