Last Updated: 12 Nov, 2020
Anagram Substring Search
Moderate
Asked in companies
Given two strings ‘STR’ and ‘PTR’. Find all the starting indices of ‘PTR’ anagram substring in ‘STR’. Two strings are anagram if and only if one string can be converted into another string by rearranging the character.
For example, ‘ABCD’ and ‘ACBD’ are two anagram strings because ‘ACBD’ can be converted into ‘ABCD’ by rearranging the ‘B’ and ‘C’. ’ABA’ and ‘ABB’ are not anagram because we can’t convert ‘ABA’ to ‘ABB’ by rearranging the characters of particular strings.
‘ABACD’ and ‘CABAD’ are anagram because ‘ABACD’ can be converted into ‘CABAD’ by rearranging the first ‘A’ with ‘C’ and second ‘A’ with ‘B’.
Note:
Strings ‘STR’ and ‘PTR’ consist only of English uppercases.
Length of string ‘STR’ will always be greater than or equal to the length of string ‘PTR’.
The index is ‘0’ based.
In case, there is no anagram substring then return an empty sequence.
Explanation:
For example, the given ‘STR’ is ‘BACDGABCD’ and ‘PTR’ is ‘ABCD’. Indices are given
0-3 in ‘STR’ index 0,1,2,3 are ‘BACD’ and it is an anagram with ‘ABCD’
1-4 in ‘STR’ index 1,2,3,4 are ‘ACDG’ and it is not anagram with ‘ABCD’
2-5 in ‘STR’ index 2,3,4,5 are ‘CDGA’ and it is not anagram with ‘ABCD’
3-6 in ‘STR’ index 3,4,5,6 are ‘DGAB’ and it is not anagram with ‘ABCD’
4-7 in ‘STR’ index 4,5,6,7 are ‘GABC’ and it is not anagram with ‘ABCD’
5-8 in ‘STR’ index 5,6,7,8 are ‘ABCD’ and it is an anagram with ‘ABCD’
Hence there are 2 starting indices of substrings in the string ‘STR’ that are anagram with given ‘PTR’ which are index 0 and 5.
Input format:
The first line of input contains an integer ‘T’ denoting the number of test cases.
The next ‘3*T’ lines represent the ‘T’ test cases.
The first line of each test case contains two 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’ on a separate line .
The third line of each test case contains the string ‘PTR’ on a separate line.
Output Format
For each test case, print a sequence of all the starting indices of the anagram substrings present in the given word/string ‘STR’.
The output of each test case will be printed in a separate line.
Note:
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints:
1 <= 'T' <= 50
1 <= 'N', 'M' <= 10 ^ 4
Where ‘T’ is the total number of test cases, ‘N’ denotes the number of characters in the first given string ‘STR’ and ‘M’ denotes the number of characters in the second given string ‘PTR’. Strings ‘STR’ and ‘PTR’ only consist of English uppercase alphabets.
Time limit: 1 second.
Approaches
- We use two loops.
- Consider ‘N’ is the number of characters in the given strings ‘STR’ and ‘M’ is the number of characters in the given string ‘PTR’.
- The outer loop runs from 0 to ‘N - M - 1’ for starting indices ‘I’ of anagram.
For each character of ‘STR’, we iterate from ‘I’ to ‘I + M -1’ and check for an anagram with the given string ‘PTR’. - For checking, we will sort all characters of ‘STR’ from ‘I’ to ‘I + M - 1’ with help of another temporary character array and check if all characters of ‘STR’ and ‘PTR’ are the same or not.
- If all characters of ‘STR’ and ‘PTR’ are the same then we will consider ‘I’ in our ‘ANSWER’ sequence, in which we are storing all the starting indices of anagram.
- Then check for the next ‘I’
- Finally, return the ‘ANSWER’ sequence.
- Consider ‘N’ is the number of characters in the given string ‘STR’ and ‘M’ is the number of characters in the given string ‘PTR’.
- We use array ‘STRMAP’ to store the frequency of characters in ‘STR’ and ‘PTRMAP’ to store the frequency of characters in ‘PTR’.
- Initial size of ‘STRMAP’ and ‘PTRMAP’ is 26 and the value is ‘0’.
- Iterate ‘i’ from 0 to ‘M - 1’ and store character if characters at ‘str[i]’ is ‘A’ then the value of ‘STRMAP[0]’ will increase by one if ‘STR[I]’ is ‘B’ then the value of ‘STRMAP[1]’ will increase by one same for all characters and do the same step for ‘PTRMAP’.
- Check if ‘STRMAP’ and ‘PTRMAP’ are the same or not, if both are the same then add ‘0’ in the ‘answer’ sequence in which we store all the starting indices of anagram.
- Now iterate ‘I’ from ‘M’ to ‘N - 1’.
In ‘STRMAP’ decrease the value of ‘STR[I - M]’ and increase the value of ‘STR[I]’ by one.
- In every iteration check if ‘STRMAP’ and ‘PTRMAP’ are the same or not, if same then add ‘I - M + 1’ in the ‘ANSWER’ sequence.
- Now iterate ‘I’ from ‘M’ to ‘N - 1’.
- Finally, return the ‘ANSWER’ sequence.