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.
1import java.util.*;
2
3class Solution {
4 public int distinctSubseqII(String s) {
5 int n = s.length();
6 final int MOD = 1_000_000_007;
7 int[] dp = new int[n + 1];
8 dp[0] = 1;
9 Map<Character, Integer> lastIndex = new HashMap<>();
10
11 for (int i = 0; i < n; i++) {
12 dp[i + 1] = (dp[i] * 2) % MOD;
13 char c = s.charAt(i);
14 if (lastIndex.containsKey(c)) {
15 dp[i + 1] = (dp[i + 1] - dp[lastIndex.get(c)] + MOD) % MOD;
16 }
17 lastIndex.put(c, 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 System.out.println(sol.distinctSubseqII("abc")); // Output: 7
26 }
27}In the Java solution, we apply dynamic programming and utilize a HashMap to track the last seen index of each character. This information is used to adjust our subsequence count.
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.