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.
"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
Knowing yesterday's solution was already magic, I didn't even attempt to do this one.
Language: javascript(2026-09-07 07:30)DONE
CPU Performance58.33%
Memory Performance75.00%
/**
* @param {string} s
* @return {number}
*/
var distinctSubseqII = function (s) {
let MOD = 1_000_000_007;
let n = s.length;
const dp = new Array(n + 1);
dp[0] = 1;
const last = Array(26).fill(-1);
for (let i = 0; i < n; ++i) {
const pos = s.charCodeAt(i) - 97;
dp[i + 1] = (dp[i] * 2) % MOD;
if (last[pos] >= 0) {
dp[i + 1] -= dp[last[pos]];
}
dp[i + 1] %= MOD;
last[pos] = i;
}
return (dp[n] - 1 + MOD) % MOD;
};