Find All Anagrams in a String
MedPrompt
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.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach iterates through every possible substring of s that has the same length as p. For each substring, it checks if it's an anagram of p by sorting both the substring and p and comparing the results.
Algorithm
- Get the lengths of
sandp, let's saynandm. - If
n < m, return an empty list as no anagram is possible. - Convert
pto a character array and sort it. This sorted array will be our reference. - Initialize an empty list
resultto store the starting indices. - Loop with an index
ifrom0ton - m. - In the loop, get the substring of
sof lengthmstarting ati. - Convert this substring to a character array and sort it.
- Compare the sorted substring's character array with the sorted
p's character array. - If they are identical, add
ito theresultlist. - After the loop, return the
resultlist.
Walkthrough
The core idea is that two strings are anagrams if and only if their sorted versions are identical. We first sort the pattern string p once to have a reference. Then, we iterate through the string s from the beginning up to the last possible starting point for a substring of p's length. In each iteration, we extract the substring, convert it to a character array, sort it, and then compare this sorted character array with the pre-sorted pattern p's character array. If they match, we've found an anagram, and we add the starting index of the substring to our result list.
import java.util.ArrayList;import java.util.Arrays;import java.util.List; class Solution { public List<Integer> findAnagrams(String s, String p) { int n = s.length(); int m = p.length(); List<Integer> result = new ArrayList<>(); if (n < m) { return result; } char[] pChars = p.toCharArray(); Arrays.sort(pChars); for (int i = 0; i <= n - m; i++) { String sub = s.substring(i, i + m); char[] sChars = sub.toCharArray(); Arrays.sort(sChars); if (Arrays.equals(pChars, sChars)) { result.add(i); } } return result; }}Complexity
Time
O((n - m) * m log m), where `n` is the length of `s` and `m` is the length of `p`. The loop runs `n - m` times. Inside the loop, creating a substring takes O(m) and sorting it takes O(m log m).
Space
O(m), where `m` is the length of the pattern string `p`. This space is required to store the character arrays for `p` and the current substring.
Trade-offs
Pros
Simple to understand and implement.
Cons
Very inefficient due to the repeated sorting of substrings.
Likely to result in a 'Time Limit Exceeded' error on most online judges for larger inputs.
This is an optimization over the sorting approach. Instead of sorting, we check for anagrams by comparing character frequency counts. We iterate through all substrings of s with length p, and for each one, we build a frequency map and compare it to the frequency map of p.
Algorithm
- Get the lengths of
sandp,nandm. - If
n < m, return an empty list. - Create a frequency map for
p(e.g., an arraypFreqof size 26 for lowercase English letters). - Initialize an empty list
result. - Loop with an index
ifrom0ton - m. - In the loop, create a frequency map for the substring
s.substring(i, i + m)(e.g., an arraysFreqof size 26). - Compare
pFreqandsFreq. - If they are identical, add
ito theresultlist. - After the loop, return
result.
Walkthrough
Two strings are anagrams if they have the same characters with the same frequencies. We can represent these frequencies using a hash map or, since the characters are lowercase English letters, a simple array of size 26. First, we compute the frequency map for the pattern p. Then, we iterate through s, considering each window of size m (length of p). For each window (substring), we compute its own character frequency map from scratch. We then compare this new frequency map with the one we created for p. If the two maps are identical, the substring is an anagram, and we record its starting index. This avoids the O(m log m) sorting cost, replacing it with a more efficient O(m) cost for building the frequency map.
import java.util.ArrayList;import java.util.Arrays;import java.util.List; class Solution { public List<Integer> findAnagrams(String s, String p) { int n = s.length(); int m = p.length(); List<Integer> result = new ArrayList<>(); if (n < m) { return result; } int[] pFreq = new int[26]; for (char c : p.toCharArray()) { pFreq[c - 'a']++; } for (int i = 0; i <= n - m; i++) { int[] sFreq = new int[26]; for (int j = 0; j < m; j++) { sFreq[s.charAt(i + j) - 'a']++; } if (Arrays.equals(pFreq, sFreq)) { result.add(i); } } return result; }}Complexity
Time
O((n - m) * m). The outer loop runs `n - m` times, and the inner loop to build the frequency map for the substring runs `m` times.
Space
O(1) or O(k) where `k` is the alphabet size (26 in this case). We use two fixed-size arrays for the frequency maps, so the space is constant.
Trade-offs
Pros
More efficient than the sorting approach.
Avoids the expensive sorting operation.
Cons
Still inefficient due to redundant computations.
The frequency map for each window is built from scratch, while adjacent windows share most of their characters.
This is the most optimal approach. It uses the sliding window technique to avoid redundant calculations. We maintain a window of size p.length() and a frequency map of the characters within that window. As we slide the window one character at a time, we efficiently update the frequency map in O(1) time instead of rebuilding it.
Algorithm
- Get lengths
nandm. Ifn < m, return an empty list. - Create two frequency maps (arrays of size 26),
pFreqandsWindowFreq. - Populate
pFrequsing characters fromp. - Populate
sWindowFrequsing characters from the firstmcharacters ofs. - Initialize an empty list
result. - Compare
pFreqandsWindowFreq. If they are equal, add0toresult. - Loop with an index
ifrommton - 1. - In the loop, update
sWindowFreq:- Increment the count for the new character
s.charAt(i). - Decrement the count for the old character
s.charAt(i - m).
- Increment the count for the new character
- Compare
pFreqandsWindowFreq. If they are equal, add the start index of the current window (i - m + 1) toresult. - After the loop, return
result.
Walkthrough
The key insight is that when we slide the window from [i, i+m-1] to [i+1, i+m], we only need to account for two character changes: the character s[i] leaving the window and the character s[i+m] entering it. We start by creating a frequency map for p and for the initial window in s (from index 0 to m-1). We check if this first window is an anagram. Then, we iterate from m to the end of s. In each step, we slide the window by decrementing the count of the character that is now outside the window and incrementing the count of the new character entering the window. After each update, we compare the window's frequency map with p's frequency map. If they match, we've found an anagram and record the new window's starting index. This way, each character in s is visited a constant number of times, leading to a linear time complexity.
import java.util.ArrayList;import java.util.Arrays;import java.util.List; class Solution { public List<Integer> findAnagrams(String s, String p) { int n = s.length(); int m = p.length(); List<Integer> result = new ArrayList<>(); if (n < m) { return result; } int[] pFreq = new int[26]; int[] sWindowFreq = new int[26]; // Build frequency map for p and the first window in s for (int i = 0; i < m; i++) { pFreq[p.charAt(i) - 'a']++; sWindowFreq[s.charAt(i) - 'a']++; } // Check if the first window is an anagram if (Arrays.equals(pFreq, sWindowFreq)) { result.add(0); } // Slide the window across the rest of s for (int i = m; i < n; i++) { // Add the new character to the window sWindowFreq[s.charAt(i) - 'a']++; // Remove the character that's leaving the window sWindowFreq[s.charAt(i - m) - 'a']--; // Check if the current window is an anagram if (Arrays.equals(pFreq, sWindowFreq)) { result.add(i - m + 1); } } return result; }}Complexity
Time
O(n), where `n` is the length of string `s`. We initialize the maps in `O(m)` time. The main loop runs `n - m` times. Inside the loop, operations are constant time, except for `Arrays.equals`, which takes `O(k)` where `k` is the alphabet size (26). So, the total time is `O(m + (n-m)*k)`. Since `k` is constant, this simplifies to `O(n)`.
Space
O(1) or O(k) where `k` is the alphabet size (26). We use two fixed-size arrays for the frequency maps, which does not depend on the input string lengths.
Trade-offs
Pros
Highly efficient with linear time complexity.
Optimal solution for this problem.
Cons
Slightly more complex to implement than the brute-force approaches.
Solutions
Solution
public class Solution { public IList < int > FindAnagrams ( string s , string p ) { int m = s . Length , n = p . Length ; IList < int > ans = new List < int >(); if ( m < n ) { return ans ; } int [] cnt1 = new int [ 26 ]; int [] cnt2 = new int [ 26 ]; for ( int i = 0 ; i < n ; ++ i ) { ++ cnt1 [ p [ i ] - 'a' ]; } for ( int i = 0 , j = 0 ; i < m ; ++ i ) { int k = s [ i ] - 'a' ; ++ cnt2 [ k ]; while ( cnt2 [ k ] > cnt1 [ k ]) { -- cnt2 [ s [ j ++] - 'a' ]; } if ( i - j + 1 == n ) { ans . Add ( j ); } } return ans ; } }class Solution {public List<Integer> findAnagrams(String s, String p) { int m = s.length(), n = p.length(); List<Integer> ans = new ArrayList<>(); if (m < n) { return ans; } int[] cnt1 = new int[26]; for (int i = 0; i < n; ++i) { ++cnt1[p.charAt(i) - 'a']; } int[] cnt2 = new int[26]; for (int i = 0; i < n - 1; ++i) { ++cnt2[s.charAt(i) - 'a']; } for (int i = n - 1; i < m; ++i) { ++cnt2[s.charAt(i) - 'a']; if (Arrays.equals(cnt1, cnt2)) { ans.add(i - n + 1); } --cnt2[s.charAt(i - n + 1) - 'a']; } return ans; }}class Solution {public: vector<int> findAnagrams(string s, string p) { int m = s.size(), n = p.size(); vector<int> ans; if (m < n) { return ans; } vector<int> cnt1(26); for (char &c : p) { ++cnt1[c - 'a']; } vector<int> cnt2(26); for (int i = 0; i < n - 1; ++i) { ++cnt2[s[i] - 'a']; } for (int i = n - 1; i < m; ++i) { ++cnt2[s[i] - 'a']; if (cnt1 == cnt2) { ans.push_back(i - n + 1); } --cnt2[s[i - n + 1] - 'a']; } return ans; }};class Solution: def findAnagrams(self, s: str, p: str) -> List[int]: m, n = len(s), len(p) ans = [] if m < n: return ans cnt1 = Counter(p) cnt2 = Counter(s[: n - 1]) for i in range(n - 1, m): cnt2[s[i]] += 1 if cnt1 == cnt2: ans . append(i - n + 1) cnt2[s[i - n + 1]] -= 1 return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.