1960. Maximum Product of the Length of Two Palindromic Substrings Hard

1/**
2 * [1960] Maximum Product of the Length of Two Palindromic Substrings
3 *
4 * You are given a 0-indexed string s and are tasked with finding two non-intersecting palindromic substrings of odd length such that the product of their lengths is maximized.
5 * More formally, you want to choose four integers i, j, k, l such that 0 <= i <= j < k <= l < s.length and both the substrings s[i...j] and s[k...l] are palindromes and have odd lengths. s[i...j] denotes a substring from index i to index j inclusive.
6 * Return the maximum possible product of the lengths of the two non-intersecting palindromic substrings.
7 * A palindrome is a string that is the same forward and backward. A substring is a contiguous sequence of characters in a string.
8 *  
9 * Example 1:
10 * 
11 * Input: s = "ababbb"
12 * Output: 9
13 * Explanation: Substrings "aba" and "bbb" are palindromes with odd length. product = 3 * 3 = 9.
14 * 
15 * Example 2:
16 * 
17 * Input: s = "zaaaxbbby"
18 * Output: 9
19 * Explanation: Substrings "aaa" and "bbb" are palindromes with odd length. product = 3 * 3 = 9.
20 * 
21 *  
22 * Constraints:
23 * 
24 * 	2 <= s.length <= 10^5
25 * 	s consists of lowercase English letters.
26 * 
27 */
28pub struct Solution {}
29
30// problem: https://leetcode.com/problems/maximum-product-of-the-length-of-two-palindromic-substrings/
31// discuss: https://leetcode.com/problems/maximum-product-of-the-length-of-two-palindromic-substrings/discuss/?currentPage=1&orderBy=most_votes&query=
32
33// submission codes start here
34
35impl Solution {
36    pub fn max_product(s: String) -> i64 {
37        
38    }
39}
40
41// submission codes end
42
43#[cfg(test)]
44mod tests {
45    use super::*;
46
47    #[test]
48    fn test_1960() {
49    }
50}
51