1930. Unique Length-3 Palindromic Subsequences Medium

1/**
2 * [1930] Unique Length-3 Palindromic Subsequences
3 *
4 * Given a string s, return the number of unique palindromes of length three that are a subsequence of s.
5 * Note that even if there are multiple ways to obtain the same subsequence, it is still only counted once.
6 * A palindrome is a string that reads the same forwards and backwards.
7 * A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.
8 * 
9 * 	For example, "ace" is a subsequence of "<u>a</u>b<u>c</u>d<u>e</u>".
10 * 
11 *  
12 * Example 1:
13 * 
14 * Input: s = "aabca"
15 * Output: 3
16 * Explanation: The 3 palindromic subsequences of length 3 are:
17 * - "aba" (subsequence of "<u>a</u>a<u>b</u>c<u>a</u>")
18 * - "aaa" (subsequence of "<u>aa</u>bc<u>a</u>")
19 * - "aca" (subsequence of "<u>a</u>ab<u>ca</u>")
20 * 
21 * Example 2:
22 * 
23 * Input: s = "adc"
24 * Output: 0
25 * Explanation: There are no palindromic subsequences of length 3 in "adc".
26 * 
27 * Example 3:
28 * 
29 * Input: s = "bbcbaba"
30 * Output: 4
31 * Explanation: The 4 palindromic subsequences of length 3 are:
32 * - "bbb" (subsequence of "<u>bb</u>c<u>b</u>aba")
33 * - "bcb" (subsequence of "<u>b</u>b<u>cb</u>aba")
34 * - "bab" (subsequence of "<u>b</u>bcb<u>ab</u>a")
35 * - "aba" (subsequence of "bbcb<u>aba</u>")
36 * 
37 *  
38 * Constraints:
39 * 
40 * 	3 <= s.length <= 10^5
41 * 	s consists of only lowercase English letters.
42 * 
43 */
44pub struct Solution {}
45
46// problem: https://leetcode.com/problems/unique-length-3-palindromic-subsequences/
47// discuss: https://leetcode.com/problems/unique-length-3-palindromic-subsequences/discuss/?currentPage=1&orderBy=most_votes&query=
48
49// submission codes start here
50
51impl Solution {
52    pub fn count_palindromic_subsequence(s: String) -> i32 {
53        0
54    }
55}
56
57// submission codes end
58
59#[cfg(test)]
60mod tests {
61    use super::*;
62
63    #[test]
64    fn test_1930() {
65    }
66}
67