1771. Maximize Palindrome Length From Subsequences Hard

1/**
2 * [1771] Maximize Palindrome Length From Subsequences
3 *
4 * You are given two strings, word1 and word2. You want to construct a string in the following manner:
5 * 
6 * 	Choose some non-empty subsequence subsequence1 from word1.
7 * 	Choose some non-empty subsequence subsequence2 from word2.
8 * 	Concatenate the subsequences: subsequence1 + subsequence2, to make the string.
9 * 
10 * Return the length of the longest palindrome that can be constructed in the described manner. If no palindromes can be constructed, return 0.
11 * A subsequence of a string s is a string that can be made by deleting some (possibly none) characters from s without changing the order of the remaining characters.
12 * A palindrome is a string that reads the same forward as well as backward.
13 *  
14 * Example 1:
15 * 
16 * Input: word1 = "cacb", word2 = "cbba"
17 * Output: 5
18 * Explanation: Choose "ab" from word1 and "cba" from word2 to make "abcba", which is a palindrome.
19 * Example 2:
20 * 
21 * Input: word1 = "ab", word2 = "ab"
22 * Output: 3
23 * Explanation: Choose "ab" from word1 and "a" from word2 to make "aba", which is a palindrome.
24 * Example 3:
25 * 
26 * Input: word1 = "aa", word2 = "bb"
27 * Output: 0
28 * Explanation: You cannot construct a palindrome from the described method, so return 0.
29 *  
30 * Constraints:
31 * 
32 * 	1 <= word1.length, word2.length <= 1000
33 * 	word1 and word2 consist of lowercase English letters.
34 * 
35 */
36pub struct Solution {}
37
38// problem: https://leetcode.com/problems/maximize-palindrome-length-from-subsequences/
39// discuss: https://leetcode.com/problems/maximize-palindrome-length-from-subsequences/discuss/?currentPage=1&orderBy=most_votes&query=
40
41// submission codes start here
42
43impl Solution {
44    pub fn longest_palindrome(word1: String, word2: 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_1771() {
57    }
58}
59