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.
1def distinctSubseqII(s: str) -> int:
2 MOD = 10**9 + 7
3 dp = [0] * (len(s) + 1)
4 dp[0] = 1
5 lastIndex = {}
6
7 for i, char in enumerate(s):
8 dp[i + 1] = (dp[i] * 2) % MOD
9 if char in lastIndex:
10 dp[i + 1] = (dp[i + 1] - dp[lastIndex[char]] + MOD) % MOD
11 lastIndex[char] = i
12
13 return (dp[len(s)] - 1) % MOD # Subtracting the empty subsequence
14
15print(distinctSubseqII("abc")) # Output: 7The Python solution utilizes a list for dynamic programming and a dictionary to track the last seen location of each character in the string. This aids in removing duplicate subsequences contributions.
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.