1771

1771. Maximize Palindrome Length From Subsequences (Hard)

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.

Related Topics:
Dynamic Programming

Similar Questions:

• Longest Palindromic Subsequence (Medium)

Solution 1. DP

// OJ: https://leetcode.com/problems/maximize-palindrome-length-from-subsequences/
// Author: github.com/lzl124631x
// Time: O(MM + NN + MN)
// Space: O(MM + NN + MN)
class Solution {
public:
    int longestPalindrome(string A, string B) {
        reverse(begin(A), end(A));
        int M = A.size(), N = B.size();
        vector<vector<int>> dp(M + 1, vector<int>(N + 1, 0));
        vector<vector<int>> X(A.size(), vector<int>(A.size(), 1)), Y(N, vector<int>(B.size(), 1));
        for (int len = 2; len <= M; ++len) {
            for (int i = 0; i <= M - len; ++i) {
                if (A[i] == A[i + len - 1]) X[i][i + len - 1] = 2 + (i + 1 <= i + len - 2 ? X[i + 1][i + len - 2] : 0);
                else X[i][i + len - 1] = max(X[i + 1][i + len - 1], X[i][i + len - 2]);
            }
        }
        for (int len = 2; len <= N; ++len) {
            for (int i = 0; i <= N - len; ++i) {
                if (B[i] == B[i + len - 1]) Y[i][i + len - 1] = 2 + (i + 1 <= i + len - 2 ? Y[i + 1][i + len - 2] : 0);
                else Y[i][i + len - 1] = max(Y[i + 1][i + len - 1], Y[i][i + len - 2]);
            }
        }
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if (A[i] == B[j]) {
                    dp[i + 1][j + 1] = 2 + max({dp[i][j], i > 0 ? X[0][i - 1] : 0, j > 0 ? Y[0][j - 1] : 0 });
                } else {
                    dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);
                }
            }
        }
        return dp[M][N];
    }
};

Solution 2. DP

// OJ: https://leetcode.com/problems/maximize-palindrome-length-from-subsequences/
// Author: github.com/lzl124631x
// Time: O((M + N)^2)
// Space: O((M + N)^2)
// Ref: https://leetcode.com/problems/maximize-palindrome-length-from-subsequences/discuss/1075453/C%2B%2B-Longest-Palindromic-Subsequence
class Solution {
    vector<vector<int>> longestPalindromeSubseq(string s) {
        int N = s.size();
        vector<vector<int>> dp(N, vector<int>(N));
        for (int i = N - 1; i >= 0; --i) {
            for (int j = i; j < N; ++j) {
                if (i == j) dp[i][j] = 1;
                else if (s[i] == s[j]) dp[i][j] = 2 + dp[i + 1][j - 1];
                else dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
        return dp;
    }
public:
    int longestPalindrome(string A, string B) {
        auto dp = longestPalindromeSubseq(A + B);
        int ans = 0;
        for (int i = 0; i < A.size(); ++i) {
            for (int j = B.size() - 1; j >= 0; --j) {
                if (A[i] == B[j]) {
                    ans = max(ans, dp[i][A.size() + j]);
                    break; // Once we find a valid palindrome starting with `A[i]`, it must be the longest among all those starting with `A[i]` because we are traversing `j` in the reverse order. So we can break here.
                }
            }
        }
        return ans;
    }
};