Task clarification

  • 75

    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?

  • 6

    Since you can choose two b from three and there are total of 3 choices,

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

  • 86

    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




    so there're totally 3.

  • 55

    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"

  • 3

    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.

  • 0

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

  • 0

    6 totally

  • 0

    That's very helpful, thanks!

  • 0

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

  • 8

    I can't believe that the statements remain unmodified.

  • 3

    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.

  • 0

    It also took me some mins to understand the problem

  • 0

    @jedihy Very confusing, huh?

  • 0

    @mircea I have totally same thought of yours

Log in to reply

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