Last Updated: 10 Dec, 2020

Find All Anagrams in a String

Easy

Asked in companies

Solve now

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.

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

Solve now

Approaches

01 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 -

We store the count of characters of ‘PTR’ in array ‘PTR_MAP’. Index of a character ‘CH’ is given by 'CH’ - ‘A’.
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.
Finally, we return ‘ANAGRAM_INDICIES’as our answer.

Solve now