#940

Distinct Subsequences II

candidate master · 1585 · lc hard +32 · verified · 44% accepted · 1,824 likes · top 26%

Description

For a string s, calculate the total count of distinct non-empty subsequences. Since the result can be very large, return it modulo 10⁹ + 7. A subsequence is formed by removing any subset of characters while keeping the remaining ones in their original order.

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".

Code

1

2

3

class Solution:
    def distinctSubseqII(self, s: str) -> int:

class Solution:
    def distinctSubseqII(self, s: str) -> int: