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 <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5#define MOD 1000000007
6
7int distinctSubseqII(char *s) {
8 int n = strlen(s);
9 long *dp = (long *)calloc(n + 1, sizeof(long));
10 int *lastIndex = (int *)calloc(26, sizeof(int));
11 memset(lastIndex, -1, 26 * sizeof(int));
12
13 dp[0] = 1; // Represents the empty subsequence
14
15 for (int i = 0; i < n; ++i) {
16 dp[i + 1] = (dp[i] * 2) % MOD;
17 if (lastIndex[s[i] - 'a'] != -1) {
18 dp[i + 1] = (dp[i + 1] - dp[lastIndex[s[i] - 'a']]) % MOD;
19 if (dp[i + 1] < 0) dp[i + 1] += MOD;
20 }
21 lastIndex[s[i] - 'a'] = i;
22 }
23
24 long result = (dp[n] - 1 + MOD) % MOD; // Subtract empty subsequence
25
26 free(dp);
27 free(lastIndex);
28 return (int)result;
29}
30
31int main() {
32 char s[] = "abc";
33 printf("%d\n", distinctSubseqII(s)); // Output: 7
34 return 0;
35}The solution uses an array dp where dp[i] represents the number of distinct subsequences using characters up to index i. We double the count of previous subsequences for each new character, as each existing subsequence can either include the new character or not. If the character has been seen before, we adjust the count to ensure subsequences are distinct by removing the contribution from its last occurrence before the current position.
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.