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.
int distinctSubseqII(string S) {
int n = S.size();
vector<int> dp(n + 1, 0);
dp[0] = 1;
unordered_map<char, int> last;
for (int i = 1;
i <= n;
i++) {
char c = S[i - 1];
dp[i] = 2 * dp[i - 1];
if (last.find(c) != last.end()) {
dp[i] -= dp[last[c] - 1];
}
last[c] = i;
}
return dp[n] - 1;
}Follow-up:
What if the input string contains only lowercase letters?
