Find All Anagrams in a String - Solution & Explanation
Problem Statement
Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order.
Example 1:
Input: s = "cbaebabacd", p = "abc" Output: [0,6] Explanation: The substring with start index = 0 is "cba", which is an anagram of "abc". The substring with start index = 6 is "bac", which is an anagram of "abc".
Example 2:
Input: s = "abab", p = "ab" Output: [0,1,2] Explanation: The substring with start index = 0 is "ab", which is an anagram of "ab". The substring with start index = 1 is "ba", which is an anagram of "ab". The substring with start index = 2 is "ab", which is an anagram of "ab".
Constraints:
1 <= s.length, p.length <= 3 * 104sandpconsist of lowercase English letters.
Approach Overview
Problem Overview: Given a string s and a pattern p, return all starting indices in s where the substring is an anagram of p. Two strings are anagrams if they contain the same characters with the same frequency, just in a different order.
Approach 1: Sliding Window with Character Count (O(n) time, O(1) space)
This approach uses a fixed-size sliding window equal to the length of p. Maintain two frequency counters: one for the pattern and one for the current window in s. As the window moves one character at a time, increment the count for the incoming character and decrement the count for the outgoing character. When both frequency arrays match, the window represents an anagram and its starting index is recorded.
The key insight is that the window size never changes. Each step performs constant-time updates on a small character frequency array (typically size 26 for lowercase letters). This makes the entire scan linear. This technique is a classic application of the sliding window pattern combined with frequency counting.
Because the alphabet size is fixed, the extra memory remains constant, giving O(1) space complexity. This method is efficient and commonly expected in interviews for substring-anagram problems.
Approach 2: HashMap with Two-Pointer Technique (O(n) time, O(k) space)
This version uses a hash table to track character frequencies of the pattern and applies a dynamic window using two pointers (left and right). Expand the right pointer while updating counts in the map. When a character exceeds the required frequency, move the left pointer forward to restore a valid window.
Whenever the window length equals the pattern length and the frequency constraints are satisfied, the current left index is an anagram start. The two-pointer structure ensures each character is processed at most twice—once when entering the window and once when leaving.
This method generalizes well when the character set is larger than lowercase letters. Instead of fixed arrays, the frequency structure is stored in a map, making it flexible for arbitrary strings. It combines ideas from string processing and hash-based frequency tracking.
Recommended for interviews: The sliding window with character count is the most direct and commonly expected solution. It demonstrates understanding of fixed-window substring problems and achieves optimal O(n) time with constant space. Implementing the hashmap + two-pointer version also shows strong control over window management and frequency tracking. Interviewers usually accept either, but the fixed sliding window is typically the cleanest implementation.
Approach 1: Sliding Window with Character Count
This approach utilizes a sliding window technique combined with character count comparisons to efficiently find all anagrams of the string p within the string s. By maintaining a window of length equal to p as we iterate through s, and by checking the frequency of characters within this window with the frequency of characters in p, we can determine if the substring is an anagram.
This Python solution initializes a counter for the string p and a sliding window counter for s of length equivalent to p. As the window slides over s, we update the count of characters within this window. If the window's character frequency matches with that of p, it implies an anagram is found and we record the starting index.
Code
Python
JavaScript
Complexity
Time Complexity: O(n) where n is the length of s, because we iterate over `s` once.
Space Complexity: O(1) since the size of the character frequency array is fixed with respect to the alphabet.
Approach 2: Hashmap with Two-pointer Technique
This approach leverages hashmaps (or dictionaries) and a two-pointer technique to find the anagrams of p in s. We maintain counts of characters using hashmaps and adjust them as the two pointers traverse through s.
This C++ solution uses unordered maps to count occurrences of characters in both p and the sliding window within s. We first count characters in the initial window and then slide the window through s. During each step, we update the counts by adding the new character and removing the old one (left behind) and check if the current window matches the character count of p.
Complexity
Time Complexity: O(n) where n is the length of `s`.
Space Complexity: O(1) if considering character frequency hashmaps to have at most 26 entries.
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Sliding Window with Character Count | Time Complexity: O(n) where n is the length of |
| Hashmap with Two-pointer Technique | Time Complexity: O(n) where n is the length of `s`. |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window with Character Count | O(n) | O(1) | Best choice when characters are limited (e.g., lowercase letters) and a fixed-size window works. |
| HashMap with Two-Pointer Technique | O(n) | O(k) | Useful when the character set is large or dynamic and array indexing is not practical. |
Video Solution
Find All Anagrams in a String - Leetcode 438 - Python • NeetCode • 119,259 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Find All Anagrams in a String easy or hard?
Find All Anagrams in a String Python/Java solution
How to solve Find All Anagrams in a String in O(n)?
What is the best approach for Find All Anagrams in a String?
Is Find All Anagrams in a String asked at Google/Amazon/Meta?
What data structure is used in Find All Anagrams in a String?
What is the time complexity of Find All Anagrams in a String?
Ready to solve this problem?
Practice Find All Anagrams in a String with our built-in code editor and test cases.
Practice on FleetCode