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.
public int distinctSubseqII(String S) {
int n = S.length();
int[] dp = new int[n + 1];
dp[0] = 1;
Map<Character, Integer> last = new HashMap<>();
for (int i = 1;
i <= n;
i++) {
char c = S.charAt(i - 1);
dp[i] = 2 * dp[i - 1];
if (last.containsKey(c)) {
dp[i] -= dp[last.get(c) - 1];
}
last.put(c, i);
}
return dp[n] - 1;
}Follow-up:
What if the input string contains only lowercase letters?
