Permutation In String
You are given two strings named str1 and str2 of length N and M respectively. Find whether string str2 contains one of the permutations of string str1 as its substring. In other words, whether there exists any permutation of string str1 that is a substring of str2.

For Example :

Input: str1 = “ab” , str2 = “aoba” Output: True 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 of input contains an integer ‘T’ denoting the number of test cases. The next ‘T’ lines represent the ‘T’ test cases. The first and only line of each test case contains two single space-separated strings str1 and str2.

Output format :

For each test case, print either “True” or “False”.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1

Question

Permutation In String

You are given two strings named str1 and str2 of length N and M respectively. Find whether string str2 contains one of the permutations of string str1 as its substring. In other words, whether there exists any permutation of string str1 that is a substring of str2.

For Example :

Input: str1 = “ab” , str2 = “aoba”
Output: True
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 of input contains an integer ‘T’ denoting the number of test cases.
The next ‘T’ lines represent the ‘T’ test cases.

The first and only line of each test case contains two single space-separated strings str1 and str2.

Output format :

 For each test case, print either “True” or “False”.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= N <= 10^4
1 <= M <= 10^4

Strings ‘str1’ and ‘str2’ consists only of lower case letters.

Time limit: 1 second

Accepted Answer

Permutation In String

Check for Base Case i.e if Length of str1 > Length of str2, return false.As substring length is always greater than or equal to permutation never small.
Generate all the permutations of the short string and then check for each permutation if this string is present as a substring of the second string or not.
Initialize a global boolean value named flag.
To generate all the permutations of the small string, we make use of generatePermutation(flag, str1, str2, index).
Steps involved in the previous function :
- The index denotes the current index of the element in a small string.
- Swap the current element with every other element in the string towards its right, so as to generate permutations.
- Recursive call to generatePermutation (flag, str1, str2, index + 1).
- While backtracking, revert the swapping done in the previous function call.

Space Complexity: O(1)Explanation:

O(N^2), where N is the size of the small string.

As the depth of the recursion tree is N. Every node of the recursion tree contains a string of maximum length N.

Time Complexity: O(1)Explanation:

O(N!), where N is the size of the small string.

In the worst case, we will be generating all the permutations of str1 i.e N! and checking for each permutation whether it exists in str2 or not.

Accepted Answer

Permutation In String

Check for Base Case i.e if Length of str1 > Length of str2, return false.
The idea behind the approach is that one string is a permutation of another string iff both strings contain the same characters and same frequencies.
We sort both the strings so that all same characters are adjacent to each other.
Sort the short string str1 and all permutations of the string str2 . Compare each and every permutation of str2. If they match completely, then return true else return false.

Space Complexity: O(1)Explanation:

O(l1), where l1 is the length of str1.

As extra space is required to store the substring of length equal to l1 in worst case str2 is itself a permutation of str1, the array of length l1 is used.

Time Complexity: O(1)Explanation:

O((l1 * log(l1)) + ((l2 - l1) * (log(l1) * l1)))

where l1 is the length of str1, l2 is the length of str2.

As, O( l1 * log(l1)) is for sorting the string str1 using quicksort.

O((l2-l1) * O(l1 * log(l1)) is the time complexity required for traversing the str1 of window size of length of str2. And in the worst case str2 is itself a permutation of str1.

Accepted Answer

Permutation In String

Check for Base Case i.e if Length of str1 > Length of str2, return false.

One string will be a permutation of another string only if both of them contain the same characters with the same frequency. Consider every possible substring in the long string str2 of the same length as that of string str1 and check the frequency of occurrence of the characters appearing in the two.If frequencies of every letter match exactly, then only str1’s permutation will be the substring of str2.

The steps involved are as follows :

Build the HashMap named map1 which contains key-value pair, where key = character of str1, and value = frequency of key in str1.
While ( i ≤ Length(str2) - Length(str1) )
Build the HashMap named map2 which contains a key-value pair.
While( j < Length(str1) )
- map2 contains key = Character at (i + j) th index of str2

If map1 equals map2

Return True

Return False

Space Complexity: O(1)Explanation:

O(1),

In the worst case, hashmap will contain no more than 26 key-value pairs.

Time Complexity: O(1)Explanation:

O(l1+ (26 * l1) * (l2 - l1)), where l1 is the length of str1, l2 is the length of str2.

As O(l1) is used to traverse the string str1 whole.

O(26 * l1 * ( l2 - l1) ) is used to create HashMap containing almost 26 keys for each window size of length (l2 - l1) .And in function mapsEqualFrequencyCheck, in the worst case you have to traverse all keys of HashMap .

Accepted Answer

Permutation In String

Check for Base Case i.e if Length of str1 > Length of str2, return false.
Make two vectors named vec1 and vec2, where vec1 contains frequencies of every letter in str1, and vec2 contains frequencies of every character in str2.
Generate vector just once for the first window in str2.
Slide the window, remove one preceding character, and add a new succeeding character to the new window.
Update the vector by just updating the indices associated with those two characters only.
Compare all the keys of every updated vector vec2 with the keys of vec1.

Space Complexity: O(1)Explanation:

O(1),

Only constant extra space i.e two vectors each of size 26 is required.

Time Complexity: O(1)Explanation:

O(l1+ 26 * (l2 - l1)), where l1 is the length of str1 and l2 is the length of str2.

As O(l1) is used to update the frequencies of characters in both vectors.

O( 26 * (l2 - l1) ) is used to traverse the whole array for each window of length(l2- l1).

Accepted Answer

Permutation In String

By updating in approach 4, instead of comparing all the elements of the vectors i.e vec1 and vec2.
For every updated vec2 corresponding to every window of str2 considered, keep a track of the number of elements that were already matching in the earlier vector and update just the count of matching elements when we shift the window towards the right.
Initialize a variable count that represents the number of characters having the same frequency in str1 and the current window in str2.
Update the count i.e increment by one when deduction of the last element in window and addition of new element in window leads to a new frequency.
Update the count i.e. decrement by one when a character’s frequency is the same before addition or removal to the window.
After sliding of the window is done, if count equals 26 i.e. all characters match exactly the same, return true.

Space Complexity: O(1)Explanation:

O(1),

Only constant extra space i.e two vectors each of size 26 is used.

Time Complexity: O(1)Explanation:

O(l1 + (l2 - l1)), where l1 is the length of str1, l2 is the length of str2.

As O(l1) is used to update the frequencies of characters in both vectors.

O(l2 - l1) is used to traverse the window of length (l2 - l1) but during traversal you only need to update the variable count .

You are given two strings named str1 and str2 of length N and M respectively. Find whether string str2 contains one of the permutations of string str1 as its substring. In other words, whether there exists any permutation of string str1 that is a substring of str2.

For Example :

Input Format:

Output format :

Note:

Constraints:

Top PeopleStrong Full Stack Developer interview questions & answers

Popular interview questions of Full Stack Developer