Find All Anagrams in a String
Last Updated: April 2, 2026
Understanding the Problem
We need to find every position in s where a contiguous substring of length p.length() is an anagram of p. Two strings are anagrams if they contain exactly the same characters with the same frequencies, just in a different order.
The key insight is that we are always looking at substrings of a fixed length (the length of p). This means the window size never changes, which makes this a perfect candidate for a fixed-size sliding window. The challenge is figuring out how to efficiently check whether the current window is an anagram of p without doing expensive work at every position.
Key Constraints:
1 <= s.length, p.length <= 3 * 10^4→ With n up to 30,000, an O(n k) approach (where k is the length of p) is fine, but O(n k log k) sorting at every position is borderline. An O(n) solution is ideal.sandpconsist of lowercase English letters → Only 26 possible characters. This means we can use a fixed-size array of 26 instead of a hash map, keeping space constant.
Approach 1: Brute Force (Sorting)
Intuition
The simplest way to check if two strings are anagrams is to sort them both and see if the sorted versions are identical. So for every possible substring of s with length equal to p, we can extract it, sort it, and compare it with the sorted version of p.
This is the approach most people think of first. It works, but sorting each substring is expensive.
Algorithm
- Sort
pto getsortedP. - For each index
ifrom0tos.length() - p.length(): - Extract the substring
s[i..i+p.length()). - Sort this substring.
- If it equals
sortedP, addito the result list. - Return the result list.
Code
- Time Complexity: O(n * k log k), where n is the length of
sand k is the length ofp. We check n - k + 1 substrings, and sorting each one takes O(k log k). - Space Complexity: O(k). We create a sorted copy of each substring of length k.
The bottleneck here is sorting every substring from scratch. Each window overlaps with the previous one by k - 1 characters, but we throw all that information away and re-sort. What if we could update the window's character information incrementally instead of recomputing it?
Approach 2: Frequency Map Comparison
Intuition
Instead of sorting, we can represent each string by its character frequency count. Two strings are anagrams if and only if their frequency counts are identical. We build a frequency map for p once, then slide a fixed-size window across s, maintaining a frequency map for the current window. When the window slides right by one position, we add the new character and remove the old one, then compare the two maps.
The comparison itself takes O(26) = O(1) time since there are only 26 lowercase letters. This is already much better than sorting.
Algorithm
- Build a frequency array
pCountof size 26 forp. - Build a frequency array
windowCountof size 26 for the first windows[0..p.length()). - If
windowCountequalspCount, add index 0 to the result. - Slide the window from index 1 to
s.length() - p.length(): - Add the new character entering the window (increment its count).
- Remove the character leaving the window (decrement its count).
- Compare
windowCountwithpCount. If they match, add the current start index. - Return the result list.
Code
- Time Complexity: O(n), where n is the length of
s. We slide the window acrosssonce. At each step, we do O(1) work to update the window and O(26) = O(1) work to compare the two frequency arrays. - Space Complexity: O(1). Two arrays of fixed size 26, independent of input size.
This approach is already O(n), but at every window position we compare all 26 entries of the two frequency arrays. What if we tracked how many characters already match so we could skip the full comparison and just update the match count incrementally?
Approach 3: Sliding Window with Match Count (Optimal)
Intuition
Building on the frequency map idea, we can avoid comparing all 26 entries at every step. The trick is to maintain a matches counter that tracks how many of the 26 characters currently have the same frequency in both the window and p.
When the window slides, at most two character frequencies change (the one entering and the one leaving). So we only need to check those two characters against their target frequency and update matches accordingly. When matches reaches 26, every character frequency lines up and we have an anagram.
This is a classic optimization pattern: instead of recomputing a global property from scratch, maintain it incrementally by handling only what changed.
The matches counter is the key insight. After incrementing or decrementing a character's count in the window, there are only two interesting cases:
- The count just became equal to the target: we gained a match, so
matches++. - The count just moved away from the target (it was equal, now it's not): we lost a match, so
matches--.
We detect the "lost a match" case by checking if the new count is exactly one more (for adds) or one less (for removes) than the target. If the count was already far from the target, neither condition triggers and matches stays the same.
When matches is 26, all characters (including those not in p, which both have count 0) have matching frequencies, meaning the window is an anagram.
Algorithm
- Build frequency arrays
pCountandwindowCountforpand the first window. - Initialize
matchesby counting how many indices (0 to 25) havepCount[i] == windowCount[i]. - Slide the window one position at a time:
- Add the new character
c_in. IncrementwindowCount[c_in]. If this made the counts equal, incrementmatches. If this broke a previous match, decrementmatches. - Remove the old character
c_out. DecrementwindowCount[c_out]. Apply the same match logic. - If
matches == 26, add the current start index to the result. - Return the result list.
Code
- Time Complexity: O(n), where n is the length of
s. We iterate throughsonce. At each step, we do O(1) work: two array updates and at most four comparisons. - Space Complexity: O(1). Two fixed-size arrays of 26 integers and a single counter, regardless of input size.