Find All Anagrams in a String

Easy
0/40
Average time to solve is 15m
profile
Contributed by
71 upvotes
Asked in companies
IntuitThought WorksAmerican Express

Problem statement

You have been given a string STR and a non-empty string PTR. Your task is to find all the starting indices of PTR’s anagram in STR.

An anagram of a string is another string which contains the same characters and is obtained by rearranging the characters.

For example: ‘SILENT’ and ‘LISTEN’ are anagrams of each other. ‘ABA’ and ‘ABB’ are not anagram because we can’t convert ‘ABA’ to ‘ABB’ by rearranging the characters of particular strings.

Note:

1. Both STR and PTR consist of English uppercase letters.
2. Length of string 'STR' will always be greater than or equal to the length of string ‘PTR’.
3. In case, there is no anagram substring, then return an empty sequence.
4. In case of more than one anagrams, return the indices in increasing order.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer 'T' representing the number of test cases or queries to be processed. Then the test case follows.

The first line of each test case contains two space-separated integers ‘N’ and ‘M’ where ‘N’ denotes the number of characters in 'STR', and ‘M’ denotes the number of characters in ‘PTR’.

The second line of each test case contains the string 'STR'. 

The third line of each test case contains the string ‘PTR’.
Output Format : 
For each test case, print a sequence of all the starting indices of the anagram substrings present in the given string 'STR'.

Print the output of each test case in a separate line.
Note : 
You do not need to print anything; it has already been taken care of. Just implement the function.
Constraints: 
1 <= T <= 100
1 <= N <= 10^5
1 <= M <= N

Time limit: 1 second
Sample Input 1 :
2
10 3
CBAEBABACD
ABC
5 2
ABADE
BA
Sample Output 1 :
0 6
0 1
Explanation For Sample Output 1:
Test Case 1:

'STR' is ‘CBAEBABACD’ and ‘PTR’ is ‘ABC’.

0-2 in 'STR' index 0,1,2 are ‘CBA’, and it is an anagram with ‘ABC’.
1-3 in 'STR' index 1,2,3 are ‘BAE’, and it is not anagram with ‘ABC’.
2-4 in 'STR' index 2,3,4 are ‘AEB’, and it is not anagram with ‘ABC’.
3-5 in 'STR' index 3,4,5 are ‘EBA’, and it is not anagram with ‘ABC’.
4-6 in 'STR' index 4,5,6 are ‘BAB’, and it is not anagram with ‘ABC’.
5-7 in 'STR' index 5,6,7 are ‘ABA’, and it is not anagram with ‘ABC’.
6-8 in 'STR' index 6,7,8 are ‘BAC’, and it is an anagram with ‘ABC’.
7-9 in 'STR' index 7,8,9 are ‘ACD’, and it is not anagram with ‘ABC’.

Hence, there are only two substrings in the given string 'STR'  that are anagram with given string  ‘PTR’ which are ‘CBA’, and ‘BAC’ and starting indices of respective anagram substrings are 0 and 6.


Test case 2:

'STR' is ‘ABADE’ and ‘PTR’ is ‘BA’.

In the given string ‘ABADE’ the substring of length 2 starting with index 0 is ‘AB’ which is an anagram with the string ‘BA’ and a substring of length 2 starting with index 1 is ‘BA’ which is also an anagram with the string ‘BA’. Because 0 and 1 are starting indices of the substrings, we print 0 and 1.
Sample Input 2:
2
10 4
BACDGABCDA
ABCD
7 1
ABABABA
A
Sample Output 2:
0 5 6
0 2 4 6
Hint

Try checking for one substring at a time.

Approaches (1)
Brute Force Approach

We have a brute force solution to this problem. We find all substrings of STR of length M (length of PTR) and store indices of those substrings in ‘ANAGRAM_INDICIES’ which are the anagrams of given string PTR.

 

Here is the complete algorithm - 

 

  1. We store the count of characters of ‘PTR’ in array ‘PTR_MAP’. Index of a character ‘CH’ is given by 'CH’ - ‘A’.
  2. Now, we traverse ‘STR’ and find all substrings of length ‘M’.
    1. For each substring, we store the count of its characters in array ‘SUB_STR_MAP’.
    2. We then compare ‘PTR_MAP’and ‘SUB_STR_MAP’.
      1. If both are identical, it means the substring is an anagram of ‘PTR’. So, we store the starting index of that substring in  ‘ANAGRAM_INDICIES’in which we store all the starting indices of anagram.
  3. Finally, we return  ‘ANAGRAM_INDICIES’as our answer.
Time Complexity

O(N*M), Where ‘N’ is the number of characters in the given string ‘STR’ and ‘M’ is the number of characters in the given string ‘PTR’.

 

STR has N-M+1 substrings of length M. We traverse over all such substrings to check if they are an anagram of PTR. This takes O(N*M) time. Therefore, the overall complexity is O(N*M).

Space Complexity

O(1), constant space is used.

 

The size of the ‘subStrMap’ and ‘ptrMap’ arrays/lists to store frequencies of characters is 26 (constant).Hence the overall complexity is O(1).

Code Solution
(100% EXP penalty)
Find All Anagrams in a String
Full screen
Console