940. Distinct Subsequences II

Hard

1.5K

33

Given a string s, return *the number of distinct non-empty subsequences of*

`s`

. Since the answer may be very large, return it `10`^{9} + 7

.`"ace"`

is a subsequence of `"`__a__b__c__d__e__"

while `"aec"`

is not.

**Example 1:**

Input:s = "abc"Output:7Explanation:The 7 distinct subsequences are "a", "b", "c", "ab", "ac", "bc", and "abc".

**Example 2:**

Input:s = "aba"Output:6Explanation:The 6 distinct subsequences are "a", "b", "ab", "aa", "ba", and "aba".

**Example 3:**

Input:s = "aaa"Output:3Explanation:The 3 distinct subsequences are "a", "aa" and "aaa".

**Constraints:**

`1 <= s.length <= 2000`

`s`

consists of lowercase English letters.

Accepted

33.4K

Submissions

76.4K

Acceptance Rate

43.7%

Seen this question in a real interview before?

1/4

Yes

No

Discussion (0)

Related Topics

Copyright ©️ 2023 LeetCode All rights reserved