Maximize Palindrome Length From Subsequences
You are given two strings, word1 and word2. You want to construct a string in the following manner:
- Choose some non-empty subsequence
subsequence1fromword1. - Choose some non-empty subsequence
subsequence2fromword2. - Concatenate the subsequences:
subsequence1 + subsequence2, to make the string.
Return the length of the longest palindrome that can be constructed in the described manner. If no palindromes can be constructed, return 0.
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.
A palindrome is a string that reads the same forward as well as backward.
Example 1
Input
word1 = "cacb", word2 = "cbba"Output
5Choose "ab" from word1 and "cba" from word2 to make "abcba", which is a palindrome.
Example 2
Input
word1 = "ab", word2 = "ab"Output
3Choose "ab" from word1 and "a" from word2 to make "aba", which is a palindrome.
Constraints
- 1 <= word1.length, word2.length <= 1000
- word1 and word2 consist of lowercase English letters.