Find All Anagrams in a String

6 min readFeb 6, 2023

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.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

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 * 104
s and p consist of lowercase English letters.

Solution -

But if you carefully observe what the question is saying you will found out that. There is English lower-case alphabet present in string from “a-z”

As the range is specify, there is no need for using HashMap. Because in HashMap whatever character is present b/w “a-z”. It won’t care & give you the answer in O(N).
But we have given that, character are from “a-z”, we won't use HashMap there is much better way to solve this problem.

What we will do is, we will create 2 arrays. Array1 for string s & Array2 for string p. And their size would be 26. what they are storing the frequency of string s & string p.

Our first job is to store frequency of string p.
So, a count is 1 time we update frequency of a in array, b count is 1 time we update frequency of b in array & c as well count is 1 time we update frequency of c in array. If let's say there is more c furteher we will update it's frequency to 2.
The length of “p” is 3 we will store it’s length in let’s say “m” variable & by that we will take 3 character’s from string “s” & update their frequency in Array1 (s)

Now what we will do is, compare both the array of 26 size ! Are they equal? Yes, they are equal with same frequency of same character’s. Thus, it's an anagram at index 0

Now what we will do create 2 pointer’s. 1st pointer of blue color at 0th index which job is to exclude [decrement] the frequency. 2nd pointer of red color at 3rd index whose job is to include [increment] the frequency.

By that we will create a constant window of 3 size
Now we will add “e” & remove “c” from array & update their frequency. And in every step we have to compare are they equal? So, they are not equal. It’s not an anagram.

Now we will add “b” & remove “b” from array & update their frequency. And in every step we have to compare are they equal? So, they are not equal. It’s not an anagram

Now we will add “a” & remove “a” from array & update their frequency. And in every step we have to compare are they equal? So, they are not equal. It’s not an anagram

Now we will add “b” & remove “e” from array & update their frequency. And in every step we have to compare are they equal? So, they are not equal. It’s not an anagram.

Now we will add “a” & remove “b” from array & update their frequency. And in every step we have to compare are they equal? So, they are not equal. It’s not an anagram.

Now we will add “c” & remove “a” from array & update their frequency. And in every step we have to compare are they equal? So, Yes they are equal. It's an anagram & we get it from index 6

Now we will add “d” & remove “b” from array & update their frequency. And in every step we have to compare are they equal? So, they are not equal. It’s not an anagram.

Now we will stop. As red pointer moves out of array.

And the total anagram we have found is [ 0, 6 ]
So, we just found it without using HashMap. In Time Complexity of BigO(N).

I hope you have understood, let’s code it up!!

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> list = new ArrayList<Integer>();
        if(p.length() > s.length()) return  list; // Base Condition
       
            int N=s.length(); // Array1 of s
            int M=p.length(); // Array2 of p
            int[]count = freq(p); // intialize only 1 time
            
            int[]currentCount = freq(s.substring(0, M)); // freq function, update every-time according to sliding window
            
            if(areSame(count,currentCount)) // areSame function
                list.add(0);
        
            int i;
            for(i=M;i<N;i++){ // going from 3 to 9 in above example
                currentCount[s.charAt(i-M) - 'a']--; // blue pointer, decrement frequency
                currentCount[s.charAt(i)-'a']++; // red pointer, increment frequency
                if(areSame(count,currentCount)){ // now check, both array are same
                    list.add(i-M+1); // if we find similar add their index in our list
                }
            }
        return list;
    }
    private boolean areSame(int[] x, int[] y){
        for(int i = 0; i < 26; i++){
            if(x[i] != y[i]) // compare all the frequency & doesnn't find any di-similar frequency return true otherwise false
                return false;
        }
        
        return true;
    }
  private int[] freq(String s){
        int[] count = new int[26]; // create array of size 26
        for(int i = 0; i < s.length(); i++){
            count[s.charAt(i) - 'a']++; // update acc. to it's frequency
        }
        
        return count; // and return count 
    }
}

Find All Anagrams in a String

Written by Jaydeep