LeetCode 940: Distinct Subsequences II
Problem Description
Explanation
To solve this problem, we can use dynamic programming. Let dp[i] represent the number of distinct subsequences that can be formed using the first i characters of the string s. We can update dp[i] based on the following conditions:
- If s[i] has not occurred before, dp[i] = 2 * dp[i-1] + 1.
- If s[i] has occurred before, we need to subtract the last occurrence of s[i] from the total, so dp[i] = 2 * dp[i-1] - dp[last_occurrence].
We also need to keep track of the last occurrence of each character to calculate dp[i] efficiently.
Time complexity: O(n) Space complexity: O(n)
Solutions
class Solution {
public int distinctSubseqII(String s) {
int mod = (int)1e9 + 7;
int n = s.length();
int[] dp = new int[n + 1];
int[] lastOccurrence = new int[26];
Arrays.fill(lastOccurrence, -1);
dp[0] = 1;
for (int i = 1; i <= n; i++) {
dp[i] = (2 * dp[i - 1]) % mod;
int idx = s.charAt(i - 1) - 'a';
if (lastOccurrence[idx] != -1) {
dp[i] = (dp[i] - dp[lastOccurrence[idx]] + mod) % mod;
}
lastOccurrence[idx] = i - 1;
}
return (dp[n] - 1 + mod) % mod;
}
}Related LeetCode Problems
Loading editor...