Formatted question description: https://leetcode.ca/all/1771.html

# 1771. Maximize Palindrome Length From Subsequences

## Level

Hard

## 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:**

**Input:** word1 = “cacb”, word2 = “cbba”

**Output:** 5

**Explanation:** Choose “ab” from word1 and “cba” from word2 to make “abcba”, which is a palindrome.

**Example 2:**

**Input:** word1 = “ab”, word2 = “ab”

**Output:** 3

**Explanation:** Choose “ab” from word1 and “a” from word2 to make “aba”, which is a palindrome.

**Example 3:**

**Input:** word1 = “aa”, word2 = “bb”

**Output:** 0

**Explanation:** You cannot construct a palindrome from the described method, so return 0.

**Constraints:**

`1 <= word1.length, word2.length <= 1000`

`word1`

and`word2`

consist of lowercase English letters.

## Solution

Concatenate `word1`

and `word2`

to form `concat`

, and use dynamic programming to find the palindrome subsequences of `concat`

. For each palindrome, if the first character is from `word1`

and the last character is from `word2`

(use indices to check this), then it is a valid palindrome, so update the maximum length of palindrome subsequences. Finally, return the maximum length.

```
class Solution {
public int longestPalindrome(String word1, String word2) {
StringBuffer sb = new StringBuffer();
sb.append(word1);
sb.append(word2);
String concat = sb.toString();
int length1 = word1.length(), length2 = word2.length(), length3 = concat.length();
int[][] dp = new int[length3][length3];
boolean[][] twoParts = new boolean[length3][length3];
for (int i = 0; i < length3; i++) {
dp[i][i] = 1;
twoParts[i][i] = false;
}
int maxLength = 0;
for (int i = length3 - 2; i >= 0; i--) {
for (int j = i + 1; j < length3; j++) {
if (concat.charAt(i) == concat.charAt(j)) {
dp[i][j] = dp[i + 1][j - 1] + 2;
twoParts[i][j] = twoParts[i + 1][j - 1];
if (!twoParts[i][j])
twoParts[i][j] = i < length1 && j >= length1;
} else {
if (dp[i][j - 1] >= dp[i + 1][j]) {
dp[i][j] = dp[i][j - 1];
twoParts[i][j] = twoParts[i][j - 1];
}
if (dp[i][j - 1] <= dp[i + 1][j]) {
dp[i][j] = dp[i + 1][j];
twoParts[i][j] = twoParts[i][j] || twoParts[i + 1][j];
}
}
if (twoParts[i][j])
maxLength = Math.max(maxLength, dp[i][j]);
}
}
return maxLength;
}
}
```