2002. Maximum Product of the Length of Two Palindromic Subsequences Medium

1/**
2 * [2002] Maximum Product of the Length of Two Palindromic Subsequences
3 *
4 * Given a string s, find two disjoint palindromic subsequences of s such that the product of their lengths is maximized. The two subsequences are disjoint if they do not both pick a character at the same index.
5 * Return the maximum possible product of the lengths of the two palindromic subsequences.
6 * A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters. A string is palindromic if it reads the same forward and backward.
7 *  
8 * Example 1:
9 * <img alt="example-1" src="https://assets.leetcode.com/uploads/2021/08/24/two-palindromic-subsequences.png" style="width: 550px; height: 124px;" />
10 * Input: s = "leetcodecom"
11 * Output: 9
12 * Explanation: An optimal solution is to choose "ete" for the 1^st subsequence and "cdc" for the 2^nd subsequence.
13 * The product of their lengths is: 3 * 3 = 9.
14 * 
15 * Example 2:
16 * 
17 * Input: s = "bb"
18 * Output: 1
19 * Explanation: An optimal solution is to choose "b" (the first character) for the 1^st subsequence and "b" (the second character) for the 2^nd subsequence.
20 * The product of their lengths is: 1 * 1 = 1.
21 * 
22 * Example 3:
23 * 
24 * Input: s = "accbcaxxcxx"
25 * Output: 25
26 * Explanation: An optimal solution is to choose "accca" for the 1^st subsequence and "xxcxx" for the 2^nd subsequence.
27 * The product of their lengths is: 5 * 5 = 25.
28 * 
29 *  
30 * Constraints:
31 * 
32 * 	2 <= s.length <= 12
33 * 	s consists of lowercase English letters only.
34 * 
35 */
36pub struct Solution {}
37
38// problem: https://leetcode.com/problems/maximum-product-of-the-length-of-two-palindromic-subsequences/
39// discuss: https://leetcode.com/problems/maximum-product-of-the-length-of-two-palindromic-subsequences/discuss/?currentPage=1&orderBy=most_votes&query=
40
41// submission codes start here
42
43impl Solution {
44    pub fn max_product(s: String) -> i32 {
45        0
46    }
47}
48
49// submission codes end
50
51#[cfg(test)]
52mod tests {
53    use super::*;
54
55    #[test]
56    fn test_2002() {
57    }
58}
59