Substring Permutation

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
4 upvotes
Asked in company
Facebook

Problem statement

You are given a string S of length N and an array of strings ARR. All the strings in ARR are of the same length K. Your task is to find the number of such sub-strings in the string 'S' that is the concatenation of all the strings of ARR in some order.

For example :

Let ARR = [hot, dog] and S = "hotdoghot", there are two sub-strings that can be obtained by permutation of ARR starting from index 0 -> ‘hotdog’ and starting from the index 3 -> ‘doghot’.

Note :

1. An string C is a substring of string S if it can be obtained by deletion of several characters(possibly zero) from the beginning and the end from a string S.
2. The substring must contain all the strings in ARR only once and without any extra intervening character.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains an integer T’ denoting the number of test cases. Then the test case follows.

The first line of each test case contains three single space-separated integers ‘N’, ‘M’, ‘K’ denoting the size of the string S, length of the array/list ARR and length of each string in ARR. 

The second line of each test case contains string S.

The third line of each test case contains ‘M’ space-separated strings, denoting the elements of the array ARR.
Output Format : 
For each test case print the number of substrings that can be formed by some permutation of ARR. 

Output for each test case is printed in a separate line.
Note : 
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
1 <= N <= 1000
1 <= M <= 10
1 <= K <= 100      
String S and all the strings in ARR contain only lowercase English letters.

Time Limit: 1 sec
Sample Input 1 :
2
9 2 2 
aaabbbbaa 
aa bb
5 1 2
aaaaa
aa
Sample Output 1 :
2
4
Explanation Of Sample Input 1 :
All good substrings in test case 1 are starting at index 1, ‘aabbb’ and starting at index 5, ‘bbaa’ 
All good substring in test case 2 are starting at index 0,1,2,3
Sample Input 2 :
2
8 2 3
abcaabca    
abc bca 
6 6 1
aaaaaa
a a a a a a
Sample Output 2 :
1
1
Hint

Create a set of all the permutations of ARR. for each substring of length K*M in S check if it is present in set.

Approaches (2)
Brute Force

We will iterate through all the permutations of ARR and store them in a set. Then for each string of length of M*K check if it is there in then set.

 

The algorithm will be-

 

  1. We will iterate over all the permutations of ARR.
    1. Store them in a set
  2. We will iterate over all the substring of length M*K.
    1. We will maintain a number ‘ANS’ that stores the number of good substrings.
    2. If the string is in set increment ANS by 1.
Time Complexity

O(M!*M*K), Where M, K denotes the length of the array ARR and length of each string in ARR respectively.  

 

We are iterating over each permutation of length M*K and storing it in a set. Then we are iterating over all substrings of length M*K and searching it in the set which can be O(M!) in the worst case. Hence, overall time complexity will be O(M!*M*K).  

Space Complexity

O(M!*M*K), Where M, K denotes the length of the array ARR and length of each string in ARR respectively.  

 

We are storing every permutation of the array ARR in a set. There is M! permutations where each permutation is of length M*K. Hence, overall space complexity will be  O(M!*M*K).

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