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.
1function distinctSubseqII(s) {
2 const MOD = 1e9 + 7;
3 const dp = new Array(s.length + 1).fill(0);
4 dp[0] = 1;
5 const lastIndex = {};
6
7 for (let i = 0; i < s.length; i++) {
8 dp[i + 1] = (dp[i] * 2) % MOD;
9 if (s[i] in lastIndex) {
10 dp[i + 1] = (dp[i + 1] - dp[lastIndex[s[i]]] + MOD) % MOD;
11 }
12 lastIndex[s[i]] = i;
13 }
14
15 return (dp[s.length] - 1 + MOD) % MOD; // Subtract the empty subsequence
16}
17
18console.log(distinctSubseqII("abc")); // Output: 7The solution in JavaScript is structured similarly to other languages, utilizing an array for the dynamic programming calculations and an object to store last observed indices of the characters.
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.