Substring Permutation

Posted: 20 Feb, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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.
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
Approach 1

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.
Try Problem