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) =
rabbbittarget (string) =
rabbitReturns (int)
3Example 2
Input
source (string) =
babgbagtarget (string) =
bagReturns (int)
5Example 3
Input
source (string) =
abctarget (string) =
abcReturns (int)
1Use 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]Ready to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run