Distinct Subsequences II
HardStringDynamic ProgrammingMathSorting
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 10⁹ + 7. A subsequence of a string is a new string formed from the original by deleting some (possibly zero) characters without changing the relative order of the remaining characters.
Examples
Input:
s = "abc"Output:
7Explanation:
Distinct non-empty subsequences: 'a', 'b', 'c', 'ab', 'ac', 'bc', 'abc'.
Input:
s = "aba"Output:
6Explanation:
Distinct: 'a', 'b', 'aa', 'ab', 'ba', 'aba'.
Input:
s = "aaa"Output:
3Explanation:
Distinct: 'a', 'aa', 'aaa'.
Input:
s = "abcdef"Output:
63Explanation:
All 2⁶ - 1 = 63 non-empty subsequences are distinct since all characters differ.
Constraints
- •
1 ≤ s.length ≤ 2000 - •
s consists of lowercase English letters.