Distinct Subsequences II
Given a string S, find the number of distinct subsequences of S. A subsequence is a new string that can be formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters.
Constraints:
- 1 <= S.length <= 2000
Examples:
Input: "abc"
Output: 7
Explanation: The distinct subsequences are "a", "b", "c", "ab", "ac", "bc", and "abc".
Solutions
Dynamic Programming
The solution uses dynamic programming to calculate the number of distinct subsequences. It maintains a DP array where dp[i] represents the number of distinct subsequences of the first i characters. For each character, it doubles the number of subsequences and subtracts the number of subsequences that end with the same character.
function distinctSubseqII(S) {
let n = S.length;
let dp = new Array(n + 1).fill(0);
dp[0] = 1;
let last = {};
for (let i = 1; i <= n; i++) {
let c = S[i - 1];
dp[i] = 2 * dp[i - 1];
if (last[c] !== undefined) {
dp[i] -= dp[last[c] - 1];
}
last[c] = i;
}
return dp[n] - 1;
}
Follow-up:
What if the input string contains only lowercase letters?
