Distinct Subsequences

Given two sequences S, T, count number of unique ways in sequence S, to form a subsequence that is identical to the sequence T.

Subsequence : 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).

Example :
S = "rabbbit" T = "rabbit"

Return 3. And the formations as follows:

S1= "ra_bbit" 
S2= "rab_bit" 
S3="rabb_it"

"_" marks the removed character.

Interview Code Editor
Hints
  • Solution Approach
  • Complete Solution
1721 successful submissions.
Asked In:
  • Google
Click here to jump start your coding interview preparation