Last Updated: 18 Dec, 2020
Distinct Occurences
Moderate
Asked in companies
You are given two strings 'A' and 'B' of length 'N' and 'M' respectively, your task is to find the number of distinct occurrences of string 'B' in the string A as a subsequence.
Note:
1. A subsequence is a sequence generated from a string after deleting some characters of string without changing the order of remaining string characters.
2. 'A' and 'B' will be non-empty strings.
Input Format:
The first line of the input contains an integer 'T' denoting the number of test cases.
The first line of each test case contains two space-separated integers 'N' and 'M', the length of string 'A' and 'B' respectively.
The second line of each test case contains a string 'A'.
The third line of each test case contains a string 'B'.
Output Format:
For each test case, return an integer denoting the number of distinct occurrences of 'B' in 'A' as a subsequence.
Note :
You don't need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 100
1 <= M, N <= 100
Time limit: 1 sec
Approaches
We will start by generating all the possible subsequences of String ‘A’ using recursion. For every character there are two choices either to include it in the subsequence or not. Apply this for every character from start until we reach the end of the string. Push the subsequence into a data structure like a vector once the end of string is reached.
We will store all these subsequences in a data structure like a vector/list, also we’ll keep an integer ‘COUNT’ (which is initially equal to 0), which gives the count of the number of distinct occurrences of string ‘B’ in the string ‘A’ as a subsequence.
Traverse this data structure and check if the current element of the vector is equal to the String ‘B' or not. If it is equal to string ‘B’, increment the ‘COUNT’ by 1. Finally, return ‘COUNT’.
We will start by creating a recursive function such that it returns the count of distinct occurrences of string ‘B’ in ‘A’. We’ll create a 2 Dimensional ‘DP’ Array ‘DP[i][j]’, Where ‘M’ is the length of string ‘B’ and 'N' is the length of string ‘A’ and ‘DP[i][j]’ denotes the number of distinct occurrence of a substring of string ‘B(1..i)’ as a subsequence of the substring of string ‘A(1..j)’.
Base Cases:
- If ‘B’ is an empty string, then we’ll return 1 as an empty string can be a subsequence of all. Initialize the first row with all 1s.
- If ‘A’ is an empty string, then we’ll return 0 as no string can be the subsequence of an empty string. Initialize the first column with all 0s.
Recursive Cases:
- If the last character of ‘A’ and ‘B’ do not match, then remove the last character of ‘A’ and call the function again.
- Now if the last character of ‘A’ and ‘B’ match, then there are two possible cases:
- There is a possible subsequence where the last character of ‘A’ is a part of it.
- It is not a part of the subsequence.
- Our Answer will be the sum of both the cases(1 and 2), ‘DP[i+1][j] ’+ ‘DP[i][j]’. Call the recursive function once with the last character of both the strings removed and again with only the last character of ‘A’ removed.
- For example - String ‘A’= “banana” and String ‘B’ = “ban”, as the last characters of both the strings don't match then the answer(currently=0) is the same without that character in S. Now A = ”banan”. Now the last characters match(both are ‘n’), our answer now is the combination of two cases. Case 1 when only String A becomes “banan” and Case 2 when A = “banan” and B = “ba”. We then check both these cases individually and similarly see if the last character matches or not and make cases accordingly finally and reach our answer which is 3.
Similar problems