Distinct Subsequences

Problem

Return the number of distinct subsequences of s that equal t, counted by index choices.

Use dynamic programming where dp[i][j] counts subsequences of the first i characters of s matching the first j of t: skip s[i-1], plus add dp[i-1][j-1] when the characters match. An empty t has exactly one subsequence.

Hint

Every matching character can either be used in the subsequence or skipped.

Test cases

case 1

in: ["rabbbit","rabbit"]

expected: 3

case 2

in: ["babgbag","bag"]

expected: 5

case 3

in: ["",""]

expected: 1

case 4

in: ["abc",""]

expected: 1

case 5

in: ["abc","d"]

expected: 0

Starter codePython

def num_distinct_subsequences(s, t):
    # Your code here
    pass

5 test cases · run your code against them in the editor