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.
def distinctSubseqII(S):
n = len(S); dp = [0] * (n + 1); dp[0] = 1; last = {}; for i in range(1, n + 1):
c = S[i - 1]; dp[i] = 2 * dp[i - 1]; if c in last:
dp[i] -= dp[last[c] - 1]; last[c] = i; return dp[n] - 1Follow-up:
What if the input string contains only lowercase letters?
