Maximize Palindrome Length From Subsequences
hard · verified · 38.3% accepted · 566 likes · top 17%
Description
You are given two strings, word1 and word2. You want to construct a string in the following manner:
- Choose some non-empty subsequence subsequence1 from word1.
- Choose some non-empty subsequence subsequence2 from word2.
- 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:
Example 2:
Example 3:
Solution