Distinct Subsequences

Problem Statement

Given two strings s and t, count how many distinct subsequences of s equal t.

s = "rabbbit"
t = "rabbit"

Answer: 3

The string s has three 'b's. We can form "rabbit" by choosing any two of them:

r a b b b i t
    ^-^       → "rabbit" (use 1st and 2nd b)
    ^---^     → "rabbit" (use 1st and 3rd b)
      ^-^     → "rabbit" (use 2nd and 3rd b)