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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int DistinctSubseqII(string s) {
6 int MOD = 1000000007;
7 int n = s.Length;
8 int[] dp = new int[n + 1];
9 dp[0] = 1;
10 Dictionary<char, int> lastIndex = new Dictionary<char, int>();
11
12 for (int i = 0; i < n; i++) {
13 dp[i + 1] = (dp[i] * 2) % MOD;
14 if (lastIndex.ContainsKey(s[i])) {
15 dp[i + 1] = (dp[i + 1] - dp[lastIndex[s[i]]] + MOD) % MOD;
16 }
17 lastIndex[s[i]] = i;
18 }
19
20 return (dp[n] - 1 + MOD) % MOD; // Subtract the empty subsequence
21 }
22
23 public static void Main(string[] args) {
24 Solution sol = new Solution();
25 Console.WriteLine(sol.DistinctSubseqII("abc")); // Output: 7
26 }
27}The C# approach is quite similar, employing an array for DP and a dictionary to remember the last seen index of each character. The solution handles modular arithmetic due to the constraints.
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.
1function distinctSubseqII(s) {
2 const
In the JavaScript solution, we optimize space by not using a full dynamic programming array. Tracking the current subsequence count and last seen states of characters, it efficiently computes the answer.