Problem Description

Given two strings word1 and word2, you are allowed to select any non-empty subsequence from word1 and any non-empty subsequence from word2. Concatenate the chosen subsequences to form a new string. Your task is to return the maximum possible length of a palindrome that can be formed from such a concatenation.

• You must select at least one character from both word1 and word2.
• Each subsequence is chosen independently from its respective word (order preserved, but not necessarily contiguous).
• A palindrome is a string that reads the same forwards and backwards.
• Elements cannot be reused within the same subsequence.
• Return the length of the longest palindrome that can be formed by such a concatenation.

Thought Process

At first glance, the problem seems to ask for all possible subsequences of both words, concatenate them, and check which concatenation yields the longest palindrome. However, this brute-force approach is infeasible for even moderately sized strings due to the exponential number of subsequences.

The key insight is to realize that the palindrome must be formed by combining subsequences from both word1 and word2, and that the longest palindrome will be one where the left part comes from word1 and the right part comes from word2.

We need to find a way to efficiently compute the maximum-length palindrome that can be constructed by concatenating subsequences from both words, ensuring that at least one character from each is used.

This naturally leads us to dynamic programming (DP), specifically to a DP that computes the longest palindromic subsequence in the concatenation of word1 and word2, while ensuring both words contribute at least one character.

Solution Approach

• Step 1: Concatenate word1 and word2 to form a new string s = word1 + word2. Let n1 be the length of word1 and n2 be the length of word2.
• Step 2: Use dynamic programming to find the longest palindromic subsequence (LPS) of s. Let dp[i][j] represent the length of the LPS in the substring s[i...j].
• Step 3: To ensure both words contribute, we require that the palindrome uses at least one character from word1 and at least one from word2. We achieve this by only considering palindromic subsequences that start in word1 (i.e., i < n1) and end in word2 (i.e., j >= n1), and where s[i] == s[j].
• Step 4: For all possible pairs (i, j) where i is in word1 and j is in word2, and s[i] == s[j], compute 2 + dp[i+1][j-1] (since we're matching the two ends). Track the maximum value among all such pairs.
• Step 5: Return the maximum length found.

We use a DP matrix because it allows us to efficiently compute the LPS for all substrings, and by only considering valid endpoints (one from each word), we ensure the constraint is satisfied.

Example Walkthrough

Suppose word1 = "cacb" and word2 = "cbba".

• Concatenate: s = "cacbcbba"
• n1 = 4 (indices 0-3), n2 = 4 (indices 4-7)
• We build the DP table for all substrings of s to find the LPS.
• For each i in 0..3 (word1) and j in 4..7 (word2), if s[i] == s[j], we check 2 + dp[i+1][j-1].
• For example, s[1] == s[6] == 'a', so we consider 2 + dp[2][5]. Suppose dp[2][5] = 2, so this gives a palindrome of length 4.
• We repeat for all valid pairs and take the maximum.
• In this example, the answer is 5, corresponding to the palindrome "cabac".

Time and Space Complexity

• Brute-force: Enumerating all subsequences of both words and checking palindromicity would take exponential time: O(2^{n1 + n2}).
• Optimized DP Approach:
  • Building the DP table for all substrings of s takes O((n1+n2)^2) time and space.
  • The final step of checking all pairs (i, j) with i < n1 and j >= n1 is O(n1 * n2), which is dominated by the DP table construction.
• Space Complexity: O((n1+n2)^2) for the DP table.

Summary

This problem challenges us to maximize the length of a palindrome formed by concatenating subsequences from two words, with the constraint that both must contribute. The optimal solution uses dynamic programming to efficiently compute the longest palindromic subsequence in the combined string, while ensuring the palindrome includes characters from both words. By carefully restricting our search to palindromes that start in word1 and end in word2, we satisfy the constraints and achieve an elegant, efficient solution.

Code Implementation

class Solution:
    def longestPalindrome(self, word1: str, word2: str) -> int:
        s = word1 + word2
        n1 = len(word1)
        n2 = len(word2)
        n = n1 + n2
        dp = [[0] * n for _ in range(n)]
        for i in range(n-1, -1, -1):
            dp[i][i] = 1
            for j in range(i+1, n):
                if s[i] == s[j]:
                    dp[i][j] = 2 + dp[i+1][j-1] if j - i > 1 else 2
                else:
                    dp[i][j] = max(dp[i+1][j], dp[i][j-1])
        res = 0
        for i in range(n1):
            for j in range(n1, n):
                if s[i] == s[j]:
                    res = max(res, dp[i][j])
        return res
      

class Solution {
public:
    int longestPalindrome(string word1, string word2) {
        string s = word1 + word2;
        int n1 = word1.size(), n2 = word2.size();
        int n = n1 + n2;
        vector<vector<int>> dp(n, vector<int>(n, 0));
        for (int i = n - 1; i >= 0; --i) {
            dp[i][i] = 1;
            for (int j = i + 1; j < n; ++j) {
                if (s[i] == s[j]) {
                    dp[i][j] = (j - i > 1) ? 2 + dp[i + 1][j - 1] : 2;
                } else {
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        int res = 0;
        for (int i = 0; i < n1; ++i) {
            for (int j = n1; j < n; ++j) {
                if (s[i] == s[j]) {
                    res = max(res, dp[i][j]);
                }
            }
        }
        return res;
    }
};
      

class Solution {
    public int longestPalindrome(String word1, String word2) {
        String s = word1 + word2;
        int n1 = word1.length(), n2 = word2.length();
        int n = n1 + n2;
        int[][] dp = new int[n][n];
        for (int i = n - 1; i >= 0; --i) {
            dp[i][i] = 1;
            for (int j = i + 1; j < n; ++j) {
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = (j - i > 1) ? 2 + dp[i + 1][j - 1] : 2;
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        int res = 0;
        for (int i = 0; i < n1; ++i) {
            for (int j = n1; j < n; ++j) {
                if (s.charAt(i) == s.charAt(j)) {
                    res = Math.max(res, dp[i][j]);
                }
            }
        }
        return res;
    }
}
      

var longestPalindrome = function(word1, word2) {
    let s = word1 + word2;
    let n1 = word1.length, n2 = word2.length;
    let n = n1 + n2;
    let dp = Array.from({length: n}, () => Array(n).fill(0));
    for (let i = n - 1; i >= 0; --i) {
        dp[i][i] = 1;
        for (let j = i + 1; j < n; ++j) {
            if (s[i] === s[j]) {
                dp[i][j] = (j - i > 1) ? 2 + dp[i + 1][j - 1] : 2;
            } else {
                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }
    let res = 0;
    for (let i = 0; i < n1; ++i) {
        for (let j = n1; j < n; ++j) {
            if (s[i] === s[j]) {
                res = Math.max(res, dp[i][j]);
            }
        }
    }
    return res;
};