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
andp
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
}
}