• Could someone please clarify this problem to me?

Given a string S and a string T, count the number of distinct
subsequences of T in S.

A subsequence of a string is a new string which is formed from the
original string by deleting some (can be none) of the characters
without disturbing the relative positions of the remaining characters.
(ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

Here is an example: S = "rabbbit", T = "rabbit" count = 3

If I understood correctly, we need to find all distinct subsequences of T and see how many, if any appear in s. How does that equal to 3 in the given example?

• Since you can choose two `b` from three and there are total of 3 choices,
i.e.,

``````the first and the second
the first and the third
the second and the third``````

• I think what the questions means is try to find subsequences in S, such that the subsequence is same as T.
so in S we have

rabbit=T

rab
bit=T

ra*bbit=T

so there're totally 3.

• I don't think the problem statement is correct: "count the number of distinct subsequences of T in S"
What you really want to count is "the number of distinct subsequences of S equal to T"

• Mircea, I agree with you that the statement of this problem is very confusing.
I prefer Jing's explanation, because it makes the definition of "the distinct subsequence of S" very clear.
I give several examples to explain this:
If S=rabb T=ra, there is only one subsequence of S equal to T: ra *.
If S=rabb T=rab, there are two distinct subsequence of S equal to T: ra * b and rab *.
If S=rsabb T=rab, there are two distinct subsequence of S equal to T: r * a * b and r * ab *.
If S=rarab T=ra, there are three distinct subsequence of S equal to T: ra *, * ra *, and r * a *.
Hope this will help others.

• So, if S is "rabbbbit" and T is "rabbit", the expected result would be 6?

• yes
ra#bb#it
ra##bbit
rabb##it
rab#b#it
rab##bit
ra#b#bit
6 totally

• Typo in your comment. The third example is rabb*it=T

• I can't believe that the statements remain unmodified.

• Quote from http://www.programcreek.com/2013/01/leetcode-distinct-subsequences-total-java/ :
The problem itself is very difficult to understand. It can be stated like this:
Give a sequence S and T, how many distinct sub sequences from S equals to T?
How do you define "distinct" subsequence? Clearly, the 'distinct' here mean different operation combination, not the final string of subsequence. Otherwise, the result is always 0 or 1.

• It also took me some mins to understand the problem

• @jedihy Very confusing, huh?

• @mircea I have totally same thought of yours

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.