Sponsored
Sponsored
This approach applies dynamic programming by maintaining an array dp where dp[i] represents the number of distinct subsequences for the substring ending at the i-th character. Another structure is used to track when each character was last seen to handle duplicate contributions.
Time Complexity: O(n), where n is the length of the string as we process each character once.
Space Complexity: O(n + 26), for storing the dp array and the last seen index of each character.
1#include <iostream>
2#include <vector>
3#include <unordered_map>
4
5using namespace std;
6
7class Solution {
8public:
9 int distinctSubseqII(string s) {
10 int n = s.length();
11 const int MOD = 1e9 + 7;
12 vector<int> dp(n + 1, 0);
13 unordered_map<char, int> lastIndex;
14 dp[0] = 1;
15
16 for (int i = 0; i < n; ++i) {
17 dp[i + 1] = (dp[i] * 2) % MOD;
18 if (lastIndex.find(s[i]) != lastIndex.end()) {
19 dp[i + 1] = (dp[i + 1] - dp[lastIndex[s[i]]]) % MOD;
20 }
21 lastIndex[s[i]] = i;
22 }
23
24 return (dp[n] - 1 + MOD) % MOD; // Subtract the empty subsequence
25 }
26};
27
28int main() {
29 Solution sol;
30 cout << sol.distinctSubseqII("abc") << endl; // Output: 7
31 return 0;
32}The C++ solution uses dynamic programming where dp[i] keeps track of distinct subsequences ending at position i. A map is employed to store the last occurrence of each character to adjust duplicate contributions effectively.
This approach optimizes the space used by reducing the need for a full array for dynamic programming calculations, utilizing only necessary data to minimize space consumption.
Time Complexity: O(n), for processing each character in the string.
Space Complexity: O(26), reduced by maintaining states for each character explicitly without a full dp array.
1def distinctSubseqII(s: str) -> int
This Python solution does not use a dp array but instead keeps track of subsequences using only two variables, processing each character efficiently and reducing the space complexity significantly.