Last Updated: 28 Dec, 2020
Permutation In String
Hard
Asked in companies
You have been given two strings ‘str1’ and ‘str2’ of length N and M respectively. Your task is to check whether string ‘str2’ contains one of the permutations of string ‘str1’ as its substring.
In other words, find whether there exists any permutation of string ‘str1’ that is a substring of ‘str2’.
A string ‘x’ is a permutation of another string ‘y’ only if sorted(x) = sorted(y). For example, LISTEN is a permutation of SILENT.
Note: ‘str1’ and ‘str2’ contains only lowercase English Alphabet letters.
For Example :
Input: str1 = “ab” , str2 = “aoba”
Output: Yes
Explanation: Permutations of first-string str1 i.e. “ab” are [“ab”, “ba”].
The substrings of str2, i.e. “aoba” are [“a”, “o”, “b”, “a”, “ao”, “ob”, “ba”, “aob”, “oba”, “aoba”].
The string “ba” is present in the list of substrings of string str2.
Input Format:
The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.
The first line of each test case contains two single space-separated integers ‘N’ and ‘M’ respectively.
The second line of each test case contains two single space-separated strings ‘str1’ and ‘str2’ respectively.
Output format :
For each test case, the only line of output will print “Yes” if there exists any permutation of “str1” that is a substring of “str2”. Else print “No”.
Print the output of each test case in a separate line.
Note:
You are not required to print the expected output, it has already been taken care of. Just implement the function.
Constraints:
1 <= T <= 100
1 <= N <= 5000
1 <= M <= 5000
Time limit: 1 second
Approaches
We naively generate all the permutations of string ‘str1’ and then check for each permutation if it is present as a substring of the string ‘str2’ or not.
In this approach, instead of comparing each permutation of ‘str1’ to M-N substrings of ‘str2’ we will sort each substring of ‘str2’ of size N and compare it with sorted ‘str1’.
The idea behind this approach is that one string will be a permutation of another string only if both contain the same characters the same number of times.
One string will be a permutation of another string only if both contain the same characters the same number of times.
We maintain a sliding window of size ‘N’ while traversing the string ‘str2’ left to right and include the current element in the window and remove the leftmost element if the window’s size exceeds ‘N’.
If the frequency of characters of sliding window/substring of ‘str2’ and ‘str1’ is equal, then there exists a permutation of ‘str1’ in ‘str2’.
Here is the algorithm:
- We will initialise two arrays ‘arr1’ and ‘arr2’ of size 26.
- We store the frequency of each character of string ‘str1’ in ‘arr1’.
- We store the frequency of each character of the first window/substring of size ‘N’ of string ‘str2’ in ‘arr2’.
- We now traverse the rest of the string ‘str2’.
- If arr1 == arr2 then return “Yes”.
- Remove the leftmost character, i.e. decrement the frequency by 1.
- Include the current element, i.e. increment the frequency by 1.
- Finally, we check if arr1 equals arr2. If yes, then we return “Yes” as our answer. Else, we return “No”.
The last approach can be optimised. Instead of comparing all the elements of the ‘arr1’ and ‘arr2’ for every updated ‘arr2’ corresponding to every window of ‘str2’ considered, we keep track of the number of elements which were already matching in the earlier window. We update just the count of matching elements when we shift the window towards the right.
The algorithm is similar to the previous approach with some additions. We initialise an integer variable ‘count’ to 0, that represents the count of characters of the sliding window/substring that are present in ‘str1’.
- We store the frequency of each character of the first window/substring of size ‘N’ of string ‘str2’ in ‘arr2’. Now traverse the rest of the string ‘str2’ and whenever we include the current element i.e. increment the frequency of character in ‘arr2’ by 1.
- If the frequency of the included element in ‘arr2’ is less than or equal to the frequency of that character in ‘arr1’, then increment the ‘count’ by 1.
- Whenever we exclude the leftmost element i.e. decrement the frequency of character in ‘arr2’ by 1.
- If the frequency of the removed element in ‘arr2’ is less than the frequency of that character in ‘arr1’, then decrement the ‘count’ by 1.