Math Dynamic Programming
Proficient Level

Implement the distinctSubsequenceCount method that counts how many subsequences of a source string equal a target string.

You are given a source string and a target string. Return how many different subsequences of the source are equal to the target.

A subsequence is formed by deleting zero or more characters without changing the order of the remaining characters.

Example 1
Input:
source (string) = rabbbit
target (string) = rabbit
Return:
(int) 3
Example 2
Input:
source (string) = babgbag
target (string) = bag
Return:
(int) 5
Example 3
Input:
source (string) = abc
target (string) = abc
Return:
(int) 1

Use dynamic programming where each target prefix is matched against the processed part of the source.

When the current source character does not match the current target character, the count remains unchanged. When they match, there are two choices: use this source character for the target position, or skip it. Add both possibilities.

A one-dimensional DP array can be updated from right to left to save space.

Pseudocode:

function distinctSubsequenceCount(source, target):
    dp = array of length target.length + 1 filled with 0
    dp[0] = 1
    for each charSource in source:
        for j from target.length down to 1:
            if charSource == target[j - 1]:
                dp[j] += dp[j - 1]
    return dp[target.length]
Run your code to see the result.