Problem

Submissions

Hints & solutions

Discuss

Permutation In String

Hard

0/120

Average time to solve is 20m

Contributed by

22 upvotes

Asked in companies

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1 :

2
2 5
ab ebbao
1 3 
b acd

Sample Output 1 :

Yes
No

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
3 8
abc bdbkcera
3 2
abc cb

Sample Output 2 :

No
No

Hint 1

Hint 2

Hint 3

Hint 4

Naively check for all permutations of ‘str1’ if they exist in ‘str2’ as a substring or not.

Approaches (4)

Approach 1

Approach 2

Approach 3

Approach 4

Naive Approach

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.

Time Complexity

O(N!), where N is the length of ‘str1’.

We will be generating all the permutations of ‘str1 ’which takes O(N!) time. For each permutation, we will generate M-N substrings of ‘str2’ to check if it exists as a substring. This takes O(M-N) time. As O(N!) >> O(M - N), therefore the overall time complexity is O(N!).

Space Complexity

O(N ^ 2), where N is the length of ‘str1’.

The depth of the recursion tree is N, and every node of the recursion tree contains a string of maximum length N. Hence the space complexity is O(N ^ 2).

(100% EXP penalty)

Permutation In String

Console