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 <= 2000s consists of lowercase English letters.
Solutions
Solution 1
PythonJavaC++GoTypeScriptRustC
class Solution:
def distinctSubseqII(self, s: str) -> int:
mod = 10**9 + 7
n = len(s)
dp = [[0] * 26 for _ in range(n + 1)]
for i, c in enumerate(s, 1):
k = ord(c) - ord('a')
for j in range(26):
if j == k:
dp[i][j] = sum(dp[i - 1]) % mod + 1
else:
dp[i][j] = dp[i - 1][j]
return sum(dp[-1]) % mod(code-box)
class Solution {
private static final int MOD = (int) 1e9 + 7;
public int distinctSubseqII(String s) {
int[] dp = new int[26];
for (int i = 0; i < s.length(); ++i) {
int j = s.charAt(i) - 'a';
dp[j] = sum(dp) + 1;
}
return sum(dp);
}
private int sum(int[] arr) {
int x = 0;
for (int v : arr) {
x = (x + v) % MOD;
}
return x;
}
}(code-box)
class Solution {
public:
const int mod = 1e9 + 7;
int distinctSubseqII(string s) {
vector<long> dp(26);
for (char& c : s) {
int i = c - 'a';
dp[i] = accumulate(dp.begin(), dp.end(), 1l) % mod;
}
return accumulate(dp.begin(), dp.end(), 0l) % mod;
}
};(code-box)
func distinctSubseqII(s string) int {
const mod int = 1e9 + 7
sum := func(arr []int) int {
x := 0
for _, v := range arr {
x = (x + v) % mod
}
return x
}
dp := make([]int, 26)
for _, c := range s {
c -= 'a'
dp[c] = sum(dp) + 1
}
return sum(dp)
}(code-box)
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);
}(code-box)
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
}
}(code-box)
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;
}(code-box)
Solution 2
PythonJavaC++Go
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(code-box)
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;
}
}(code-box)
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;
}
};(code-box)
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
}(code-box)
Solution 3
Python
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(code-box)
