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.
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 ; } }Video 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.