730. Count Different Palindromic Subsequences Hard

1/**
2 * [730] Count Different Palindromic Subsequences
3 *
4 * Given a string s, return the number of different non-empty palindromic subsequences in s. Since the answer may be very large, return it modulo 10^9 + 7.
5 * A subsequence of a string is obtained by deleting zero or more characters from the string.
6 * A sequence is palindromic if it is equal to the sequence reversed.
7 * Two sequences a1, a2, ... and b1, b2, ... are different if there is some i for which ai != bi.
8 *  
9 * Example 1:
10 * 
11 * Input: s = "bccb"
12 * Output: 6
13 * Explanation: The 6 different non-empty palindromic subsequences are 'b', 'c', 'bb', 'cc', 'bcb', 'bccb'.
14 * Note that 'bcb' is counted only once, even though it occurs twice.
15 * 
16 * Example 2:
17 * 
18 * Input: s = "abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba"
19 * Output: 104860361
20 * Explanation: There are 3104860382 different non-empty palindromic subsequences, which is 104860361 modulo 10^9 + 7.
21 * 
22 *  
23 * Constraints:
24 * 
25 * 	1 <= s.length <= 1000
26 * 	s[i] is either 'a', 'b', 'c', or 'd'.
27 * 
28 */
29pub struct Solution {}
30
31// problem: https://leetcode.com/problems/count-different-palindromic-subsequences/
32// discuss: https://leetcode.com/problems/count-different-palindromic-subsequences/discuss/?currentPage=1&orderBy=most_votes&query=
33
34// submission codes start here
35
36impl Solution {
37    pub fn count_palindromic_subsequences(s: String) -> i32 {
38        0
39    }
40}
41
42// submission codes end
43
44#[cfg(test)]
45mod tests {
46    use super::*;
47
48    #[test]
49    fn test_730() {
50    }
51}
52