Count the number of distinct sub-sequences of T in S

Given a string S and a string T, we have to count the number of distinct sub-sequences of T in S.
Can anyone please explain the DP approach behind solving this problem.
Here’s one basic solution i found. I am unable to understand how the sub problem is chosen in this case.

same ques was asked >>here<<

hope it is of some help…:slight_smile:


i think this link could be useful!!!


PLease look at my code.
I am just a beginner in C++
Please support if you understand…:slight_smile:
Neva mind if you have any doubts.
similer tutorial is given here

1 Like

I had seen that solution but I was unable to figure out how they reached the following solution:
f(i, j) = f(i+1, j) + (S[i] == T[j]) * f(i+1, j+1)

If you can, please explain how this bottom-up approach leads to the correct solution. It’d be of great help. Thanx :slight_smile:

If i understood correctly you are checking if a string is a sub-sequence of the other right? The question was to find the number of various sub-sequences of one string in an another string.

This is some what the same question in Hacker Rank’s this week’s contest problem.There in my code instead of printing whether it is true is false you can include a counter variable and initialize it as 0. and increment it :slight_smile:
Got it??

Where exactly do you want to put the counter because the print statement executes only once !!

And besides putting a counter wouldn’t give the correct answer. Because from what i understood from your code, you build up a string sub-sequence and compare if string s1 is equal to this newly built string or not.

Simply putting a counter will only count the length of the newly built sub-sequence and not give the answer to the “how many” sub-sequences part.

Also we have to consider that we take only DISTINCT sub-sequences into account.

did u see the 2nd link???

This is helpful… Thanx :slight_smile:

1 Like

Space optimized Dp solution along with top down recursive.
Python3 Code: Link