Distinct Occurences

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

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
12 3
codingninjas
cij
2 1
aa
b
Sample Output 1:
2
0
Explanation of Sample Output 1:
In test case 1, Possible subsequences are: [c  i     j  ], [c      i j  ].

In test case 2, There is no possible subsequence.
Sample Input 2:
2
4 2
abcd
ac
6 3
banana
ban
Sample Output 2:
1
3
Explanation of Sample Output 2:
In test case 1, Possible subsequence is: [a c ].

In test case 2, Possible subsequences are: [ban], [ba  n ],[b   an ].
Hint

Try to generate all subsequences of string ‘A’.

Approaches (2)
Brute Force Solution

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’.

Time Complexity

O(2 ^ N), Where ‘N’ is the number of characters in the string ‘A’.

 

Since there are two choices for each character whether to be included or not in the subsequence, and there are N characters so total possible subsequence of string A is 2 ^ N, hence time complexity will be O(2 ^ N). 

Space Complexity

O(2 ^ N), Where ‘N’ is the number of characters in the string ‘A’.

 

Since there are total 2 ^ N possible subsequences of string A, hence the space complexity will be O(2 ^ N).

Code Solution
(100% EXP penalty)
Distinct Occurences
Full screen
Console