Find All Anagrams in a String

LeetCode 438: Find All Anagrams in a String Solution & Explanation

Problem Overview

TL;DR: Use a fixed-size sliding window combined with frequency arrays to track character counts in linear time, comparing the current window's state against the target string's profile.

The problem asks us to locate every occurrence of an anagram of string p within a larger string s. Specifically, we need to return the starting indices of these substrings. An anagram is defined as a string containing the exact same characters with the exact same frequencies, just potentially in a different order. This is a classic application of the LeetCode 438 "Find All Anagrams in a String" problem, widely used to test understanding of efficient string manipulation and state maintenance.

Brute Force Approach for Find All Anagrams in a String

The naive approach involves checking every possible substring of s that has the same length as p to see if it is an anagram.

1. Iterate through s starting from index i = 0 up to len(s) - len(p).
2. Extract the substring sub = s[i : i + len(p)].
3. Sort both sub and p.
4. Compare the sorted strings. If they are identical, add i to the result list.

Pseudo-code:

n = length of s
m = length of p
result = []
sorted_p = sort(p)

for i from 0 to n - m:
    substring = s[i to i + m]
    if sort(substring) == sorted_p:
        result.add(i)
return result

Complexity Analysis: The time complexity is dominated by the sorting operation inside the loop. Sorting a string of length $M$ takes $O(M \log M)$. We perform this $N - M$ times. Total Time Complexity: $O((N - M) \cdot M \log M)$.

Why it fails: Given the constraints where s.length can be up to $30,000$, an $O(N \cdot M \log M)$ approach performs roughly $10^9$ operations in the worst case, leading to a Time Limit Exceeded (TLE) error. The inefficiency stems from re-processing and re-sorting the substring at every step, ignoring the fact that overlapping substrings share mostly the same characters.

Algorithm Strategy: Sliding Window Patterns

1. Input Validation: If len(p) > len(s), return an empty list immediately.
2. Frequency Initialization: Create two frequency arrays (or hashmaps) of size 26. Populate the first with characters from p. Populate the second with the first len(p) characters of s.
3. Initial Check: Compare the two frequency arrays. If they match, record index 0.
4. Sliding Phase: Iterate through s starting from index len(p) to the end.
   • Add: Include the new character at the current index i into the window's frequency array.
   • Remove: Exclude the character at index i - len(p) from the window's frequency array.
   • Check: Compare the updated window frequency array with p's frequency array. If they match, record the start index i - len(p) + 1.
5. Return: The list of recorded indices.

This strategy ensures that the "constraint" (window size equals len(p)) is always maintained, and the "invariant" (window counts reflect current substring) is updated in constant time.

Execution Flow

Let s = "cbaebabacd", p = "abc". Length of p is 3.

1. Setup:

   • p_count: {a:1, b:1, c:1, ...}
   • s_count: Initialize with first 3 chars "cba". {a:1, b:1, c:1, ...}
   • Compare: Match found. Result: [0].

2. Iteration i = 3 (Char 'e'):

   • Slide: Remove s[0] ('c'), Add s[3] ('e').
   • s_count becomes {a:1, b:1, c:0, e:1, ...}.
   • Compare with p_count: No match.

3. Iteration i = 4 (Char 'b'):

   • Slide: Remove s[1] ('b'), Add s[4] ('b').
   • s_count becomes {a:1, b:1, c:0, e:1, ...} (net change 0 for 'b').
   • Compare: No match.

4. Iteration i = 5 (Char 'a'):

   • Slide: Remove s[2] ('a'), Add s[5] ('a').
   • s_count remains {a:1, b:1, c:0, e:1, ...}.
   • Compare: No match.

5. Iteration i = 6 (Char 'b'):

   • Slide: Remove s[3] ('e'), Add s[6] ('b').
   • s_count becomes {a:1, b:2, c:0, ...}.
   • Compare: No match.

6. Iteration i = 7 (Char 'a'):

   • Slide: Remove s[4] ('b'), Add s[7] ('a').
   • s_count becomes {a:2, b:1, c:0, ...}.
   • Compare: No match.

7. Iteration i = 8 (Char 'c'):

   • Slide: Remove s[5] ('a'), Add s[8] ('c').
   • s_count becomes {a:1, b:1, c:1, ...}.
   • Compare: Match found. Result: [0, 6].

8. Iteration i = 9 (Char 'd'):

   • Slide: Remove s[6] ('b'), Add s[9] ('d').
   • s_count becomes {a:1, b:0, c:1, d:1, ...}.
   • Compare: No match.

Final Output: [0, 6].

Proof of Correctness

The algorithm is correct because it exhaustively checks every substring of length len(p).

1. Completeness: The loop runs from the start of s to the end, ensuring no window position is skipped.
2. Validity: The condition window_count == p_count is the mathematical definition of an anagram (ignoring order, preserving frequency).
3. State Maintenance: The operations window_count[new]++ and window_count[old]-- correctly transform the frequency map of substring $S_{i-1}$ to substring $S_i$. Thus, the invariant holds at every step.

Pattern Reuse Notes

The Sliding Window - Character Frequency Matching pattern is highly transferable. The following problems share the exact same logic:

• LeetCode 567: Permutation in String - This is identical to Find All Anagrams, but you return true immediately after finding the first match instead of collecting all indices.
• LeetCode 76: Minimum Window Substring - Uses a variable-size sliding window but relies on the same frequency array concept to validate the window's contents.

Reference Implementation

C++ Solution for LeetCode 438

1#include <vector>
2#include <string>
3
4using namespace std;
5
6class Solution {
7public:
8    vector<int> findAnagrams(string s, string p) {
9        vector<int> result;
10        if (s.length() < p.length()) return result;
11
12        vector<int> p_count(26, 0);
13        vector<int> s_count(26, 0);
14
15        // Initialize frequency maps for the first window
16        for (int i = 0; i < p.length(); i++) {
17            p_count[p[i] - 'a']++;
18            s_count[s[i] - 'a']++;
19        }
20
21        // Check the first window
22        if (p_count == s_count) {
23            result.push_back(0);
24        }
25
26        // Slide the window
27        for (int i = p.length(); i < s.length(); i++) {
28            // Add new character to the window
29            s_count[s[i] - 'a']++;
30            // Remove the character going out of the window
31            s_count[s[i - p.length()] - 'a']--;
32
33            // Compare maps
34            if (s_count == p_count) {
35                result.push_back(i - p.length() + 1);
36            }
37        }
38
39        return result;
40    }
41};

Java Solution for LeetCode 438

1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.List;
4
5class Solution {
6    public List<Integer> findAnagrams(String s, String p) {
7        List<Integer> result = new ArrayList<>();
8        if (s.length() < p.length()) return result;
9
10        int[] pCount = new int[26];
11        int[] sCount = new int[26];
12
13        // Initialize frequency maps
14        for (int i = 0; i < p.length(); i++) {
15            pCount[p.charAt(i) - 'a']++;
16            sCount[s.charAt(i) - 'a']++;
17        }
18
19        // Check first window
20        if (Arrays.equals(pCount, sCount)) {
21            result.add(0);
22        }
23
24        // Slide the window
25        for (int i = p.length(); i < s.length(); i++) {
26            // Add new character
27            sCount[s.charAt(i) - 'a']++;
28            // Remove old character
29            sCount[s.charAt(i - p.length()) - 'a']--;
30
31            // Compare
32            if (Arrays.equals(pCount, sCount)) {
33                result.add(i - p.length() + 1);
34            }
35        }
36
37        return result;
38    }
39}

Python Solution for LeetCode 438

1from typing import List
2
3class Solution:
4    def findAnagrams(self, s: str, p: str) -> List[int]:
5        if len(s) < len(p):
6            return []
7        
8        p_count = [0] * 26
9        s_count = [0] * 26
10        result = []
11        
12        # Initialize frequency maps
13        for i in range(len(p)):
14            p_count[ord(p[i]) - ord('a')] += 1
15            s_count[ord(s[i]) - ord('a')] += 1
16            
17        if p_count == s_count:
18            result.append(0)
19            
20        # Slide the window
21        # Start from len(p) because the first window (0 to len(p)-1) is already processed
22        for i in range(len(p), len(s)):
23            # Add new character
24            s_count[ord(s[i]) - ord('a')] += 1
25            # Remove old character
26            s_count[ord(s[i - len(p)]) - ord('a')] -= 1
27            
28            if s_count == p_count:
29                result.append(i - len(p) + 1)
30                
31        return result