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
fromword1
. - Choose some non-empty subsequence
subsequence2
fromword2
. - 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
andword2
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;
}
}