Distinct Subsequences

Easy
0/40
4 upvotes
Asked in companies
MakeMyTripInnovaccerMicrosoft

Problem statement

Given two strings S and T consisting of lower case English letters. The task is to count the distinct occurrences of T in S as a subsequence.

A subsequence is a sequence generated from a string after deleting some or no characters of the string without changing the order of the remaining string characters. (i.e. “ace” is a subsequence of “abcde” while “aec” is not).

For example, for the strings S = “banana” and T=”ban”, output is 3 as T appears in S as below three subsequences.

[ban], [ba n], [b an ]

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer ‘T’ representing the number of test cases. Then the test cases follow.

The first line of each test case contains string S consisting of lowercase English letters.

The second line of each test case contains string T consisting of lowercase English letters.
Output Format: 
For each test case, print a single integer denoting the count of distinct occurrences of T in S as a subsequence.

The output for each test case is in a separate line.
Note: 
You do not need to print anything; it has already been taken care of.
Constraints: 
1 <= T <= 10
1 <= N <= 100

Where ‘T’ is the number of test cases, and ‘N’ is the length of the strings.

Time Limit: 1sec
Sample Input 1:
2
banana
ban
babgbag
bag
Sample Output 1:
3
5
Explanation of Sample Input 1:
For the first test case, there are 3 ways we can generate “ban” from S, i.e. [ban], [ba  n], [b  an ].

For the second test case, there are 5 ways we can generate “bag” from S, i.e. [ba g   ], [ba    g], [b    ag], [  b  ag] and [    bag].
Sample Input 2:
2
rabbbit
rabbit
abcd
abe
Sample Output 2:
3
0
Hint

Recursively process all characters of both the strings from one side.

Approaches (2)
Recursive Approach

If we carefully analyze the given problem, we can see that it can be easily divided into sub-problems which can be solved using recursion. The idea is to process all characters of both strings one by one starting from either from left or right side. Let us traverse from the right corner, there are two possibilities for every pair of characters being traversed.

 

Base Cases:

  1. Given the string T is an empty string, return 1 as an empty string can be the subsequence of all.
  2. Given the string S is an empty string, return 0 as no string can be the subsequence of an empty string.

 

Recursive Cases:

  1. If the last character of S and T do not match, then remove the last character of S and call the recursive function again. Because the last character of S cannot be a part of the subsequence or remove it and check for other characters.
  2. If the last character of S matches then there can be two possibilities, first there can be a subsequence where the last character of S is a part of it and second where it is not a part of the subsequence. So the required value will be the sum of both. Call the recursive function once with the last character of both the strings removed and again with only the last character of S removed.
Time Complexity

O(2 ^ N), where ‘N’ is the length of the given string ‘S’.

 

In the worst case when all the characters in the given strings are the same, each recursive call will end up in two recursive calls. Thus, the final time complexity is O(2 ^ N).

Space Complexity

O(N), Where ‘N’ is the length of the given string ‘S’.

 

We are using O(H) extra space for the call stack where ‘H’ is the height of the recursion tree, and height of a recursion tree could be ‘N’ in the worst case, when all the characters present in the given strings are the same. Thus, the final space complexity is O(N).

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