Permutation In String

Easy
0/40
3 upvotes
Asked in companies
FreshworksDelhiveryPwC India

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
ab ebbao
b acd
Sample Output 1 :
True
False
Explanation Of the Sample Input 1 :
In the First Test Case :
Permutations of first-string str1 i.e. “ab” are [ “ab”, “ba” ].
The substrings of str2 i.e. “ebbao” are [ “e”, “b”, “b”, “a”, “o”, “eb”, “bb”,  “ba”, “ao”,  “ebb”, “bba”, “bao”,  “ebba”, “bbao”, “ebbao”  ].
The string “ba” is present in the list of substrings of string str2.

In the Second Test Case :
Permutations of first-string str1 i.e. “b” are [ “b” ].
The substrings of str2 i.e. “acd” are [ “a”, “c”, “d”, “ac”, “cd”, “acd” ]. 
The string “b” is not present in the list of substrings of string str2.
Sample Input 2 :
2
abc bdbkcera
abc cb
Sample Output 2 :
False
False
Explanation Of the Sample Input 2 :
In the Second Test Case :
Permutations of first-string str1 i.e. “abc” are [ “abc”, “bac”, “acb”, “bca”, “cab”, cba” ].
The substrings of str2 i.e. “cb” are [ “c”, “b”, “cb” ].
The string of any of the permutations of “abc”  is not present in the list of substrings of string str2.
Hint

Brute-Force Method

Approaches (5)
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.
Time Complexity

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.

Space Complexity

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.

Code Solution
(100% EXP penalty)
Permutation In String
Full screen
Console