Algorithm
Problem Name: 940. Distinct Subsequences II
Problem Link: https://leetcode.com/problems/distinct-subsequences-ii/
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.
Code Examples
#1 Code Example with Javascript Programming
Code -
Javascript Programming
const distinctSubseqII = function(s) {
const n = s.length,
dp = Array(26).fill(0),
a = 'a'.charCodeAt(0),
mod = 1e9 + 7
let res = 0
for(let ch of s) {
const idx = ch.charCodeAt(0) - a
let tmp = 0
for(let i = 0; i < 26; i++) tmp = (tmp + dp[i]) % mod
tmp = (tmp + 1) % mod
dp[idx] = tmp
}
return dp.reduce((ac, e) => (ac + e) % mod, 0)
};
Input
s = "abc"
Output
7
#2 Code Example with Python Programming
Code -
Python Programming
class Solution:
def distinctSubseqII(self, S):
res, end = 0, collections.Counter()
for c in S:
res, end[c] = res * 2 + 1 - end[c], res + 1
return res % (10**9 + 7)
Input
s = "abc"
Output
7