Welcome to Subscribe On Youtube
940. Distinct Subsequences II
Description
Given a string s, return the number of distinct non-empty subsequences of s. Since the answer may be very large, return it modulo 109 + 7.
A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not.
Example 1:
Input: s = "abc" Output: 7 Explanation: The 7 distinct subsequences are "a", "b", "c", "ab", "ac", "bc", and "abc".
Example 2:
Input: s = "aba" Output: 6 Explanation: The 6 distinct subsequences are "a", "b", "ab", "aa", "ba", and "aba".
Example 3:
Input: s = "aaa" Output: 3 Explanation: The 3 distinct subsequences are "a", "aa" and "aaa".
Constraints:
1 <= s.length <= 2000sconsists of lowercase English letters.
Solutions
Solution 1: Dynamic Programming
Definition $dp[i]$ represents the number of different subsequences ending with $s[i]$. Since $s$ contains only lowercase letters, we can directly create an array of length $26$. Initially all elements of $dp$ are $0$. The answer is $\sum_{i=0}^{25}dp[i]$.
Traverse the string $s$, for the character $s[i]$ at each position, we need to update the number of different subsequences ending with $s[i]$, at this time $dp[i]=\sum_{j=0}^{25}dp[j]+1$. Among them, $\sum_{j=0}^{25}dp[j]$ is the number of all different subsequences that we have previously calculated, and $+1$ means that $s[i]$ itself can also be used as a subsequence.
Finally, we need to sum all the elements in $dp$ and take the remainder of $10^9+7$ to get the answer.
The time complexity is $O(n\times C)$, where $n$ is the length of the string $s$, and $C$ is the size of the character set, in this question $C=26$. Space complexity $O(C)$.
Solution 2
Based on method one, we can also maintain the sum $ans$ of all elements in the current $dp$ array, so that every time we update $dp[i]$, we only need to add $dp[i]$ to $ans-dp[i]+1$.
Time complexity $O(n)$, space complexity $O(C)$.
Similar topics:
Solution 3
This implementation uses dynamic programming. It traverses the relevant values and updates its state as each value is processed. Previously computed states are retained so the same subproblem does not need to be solved again. After all required states have been considered, the maintained result is returned.
-
class Solution { private static final int MOD = (int) 1e9 + 7; public int distinctSubseqII(String s) { int[] dp = new int[26]; int ans = 0; for (int i = 0; i < s.length(); ++i) { int j = s.charAt(i) - 'a'; int add = (ans - dp[j] + 1) % MOD; ans = (ans + add) % MOD; dp[j] = (dp[j] + add) % MOD; } return (ans + MOD) % MOD; } } // Solution 2 class Solution { private static final int MOD = (int) 1e9 + 7; public int distinctSubseqII(String s) { int[] dp = new int[26]; int ans = 0; for (int i = 0; i < s.length(); ++i) { int j = s.charAt(i) - 'a'; int add = (ans - dp[j] + 1) % MOD; ans = (ans + add) % MOD; dp[j] = (dp[j] + add) % MOD; } return (ans + MOD) % MOD; } } -
class Solution { public: const int mod = 1e9 + 7; int distinctSubseqII(string s) { vector<long> dp(26); long ans = 0; for (char& c : s) { int i = c - 'a'; long add = ans - dp[i] + 1; ans = (ans + add + mod) % mod; dp[i] = (dp[i] + add) % mod; } return ans; } }; // Solution 2 class Solution { public: const int mod = 1e9 + 7; int distinctSubseqII(string s) { vector<long> dp(26); long ans = 0; for (char& c : s) { int i = c - 'a'; long add = ans - dp[i] + 1; ans = (ans + add + mod) % mod; dp[i] = (dp[i] + add) % mod; } return ans; } }; -
class Solution: def distinctSubseqII(self, s: str) -> int: mod = 10**9 + 7 dp = [0] * 26 ans = 0 for c in s: i = ord(c) - ord('a') add = ans - dp[i] + 1 ans = (ans + add) % mod dp[i] += add return ans # Solution 2 class Solution: def distinctSubseqII(self, s: str) -> int: mod = 10**9 + 7 dp = [0] * 26 for c in s: i = ord(c) - ord('a') dp[i] = sum(dp) % mod + 1 return sum(dp) % mod # Solution 3 class Solution: def distinctSubseqII(self, s: str) -> int: mod = 10**9 + 7 dp = [0] * 26 ans = 0 for c in s: i = ord(c) - ord('a') add = ans - dp[i] + 1 ans = (ans + add) % mod dp[i] += add return ans -
func distinctSubseqII(s string) int { const mod int = 1e9 + 7 dp := make([]int, 26) ans := 0 for _, c := range s { c -= 'a' add := ans - dp[c] + 1 ans = (ans + add) % mod dp[c] = (dp[c] + add) % mod } return (ans + mod) % mod } // Solution 2 func distinctSubseqII(s string) int { const mod int = 1e9 + 7 dp := make([]int, 26) ans := 0 for _, c := range s { c -= 'a' add := ans - dp[c] + 1 ans = (ans + add) % mod dp[c] = (dp[c] + add) % mod } return (ans + mod) % mod } -
function distinctSubseqII(s: string): number { const mod = 1e9 + 7; const dp = new Array(26).fill(0); for (const c of s) { dp[c.charCodeAt(0) - 'a'.charCodeAt(0)] = dp.reduce((r, v) => (r + v) % mod, 0) + 1; } return dp.reduce((r, v) => (r + v) % mod, 0); } -
impl Solution { pub fn distinct_subseq_ii(s: String) -> i32 { const MOD: i32 = (1e9 as i32) + 7; let mut dp = [0; 26]; for u in s.as_bytes() { let i = (u - &b'a') as usize; dp[i] = ({ let mut sum = 0; dp.iter().for_each(|&v| { sum = (sum + v) % MOD; }); sum }) + 1; } let mut res = 0; dp.iter().for_each(|&v| { res = (res + v) % MOD; }); res } } -
int distinctSubseqII(char* s) { int mod = 1e9 + 7; int n = strlen(s); int dp[26] = {0}; for (int i = 0; i < n; i++) { int sum = 0; for (int j = 0; j < 26; j++) { sum = (sum + dp[j]) % mod; } dp[s[i] - 'a'] = sum + 1; } int res = 0; for (int i = 0; i < 26; i++) { res = (res + dp[i]) % mod; } return res; }