940. Distinct Subsequences II Hard

1/**
2 * [940] Distinct Subsequences II
3 *
4 * 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^9 + 7.
5 * A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "<u>a</u>b<u>c</u>d<u>e</u>" while "aec" is not.
6 *  
7 * Example 1:
8 * 
9 * Input: s = "abc"
10 * Output: 7
11 * Explanation: The 7 distinct subsequences are "a", "b", "c", "ab", "ac", "bc", and "abc".
12 * 
13 * Example 2:
14 * 
15 * Input: s = "aba"
16 * Output: 6
17 * Explanation: The 6 distinct subsequences are "a", "b", "ab", "aa", "ba", and "aba".
18 * 
19 * Example 3:
20 * 
21 * Input: s = "aaa"
22 * Output: 3
23 * Explanation: The 3 distinct subsequences are "a", "aa" and "aaa".
24 * 
25 *  
26 * Constraints:
27 * 
28 * 	1 <= s.length <= 2000
29 * 	s consists of lowercase English letters.
30 * 
31 */
32pub struct Solution {}
33
34// problem: https://leetcode.com/problems/distinct-subsequences-ii/
35// discuss: https://leetcode.com/problems/distinct-subsequences-ii/discuss/?currentPage=1&orderBy=most_votes&query=
36
37// submission codes start here
38
39impl Solution {
40    pub fn distinct_subseq_ii(s: String) -> i32 {
41        0
42    }
43}
44
45// submission codes end
46
47#[cfg(test)]
48mod tests {
49    use super::*;
50
51    #[test]
52    fn test_940() {
53    }
54}
55