# Maximize Palindrome Length From Subsequences
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximize-palindrome-length-from-subsequences)
Canonical: https://scaleengineer.com/dsa/problems/maximize-palindrome-length-from-subsequences
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** String
---
## Problem
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.

# Approaches
## Brute-Force with Subsequence Generation
The most straightforward, yet highly inefficient, way to solve this problem is to generate all possible combinations of subsequences and check each one. We can generate every non-empty subsequence from `word1` and every non-empty subsequence from `word2`. For each pair of subsequences, we concatenate them and check if the resulting string is a palindrome. We keep track of the maximum length found among all palindromic constructions.
**Time:** O((n+m) * 2^(n+m)) · **Space:** O(2^n * n + 2^m * m)
**Pros:** Conceptually simple and easy to understand.; Guaranteed to find the correct answer by exhaustively checking all possibilities.
**Cons:** Extremely inefficient due to its exponential time complexity.; Not feasible for the given constraints (lengths up to 1000). It will time out for inputs larger than about 15-20 characters in total length.
### Explanation
The algorithm proceeds as follows:

1.  Initialize `maxLength = 0`.
2.  Generate all non-empty subsequences of `word1`. Let's call this set `S1`.
3.  Generate all non-empty subsequences of `word2`. Let's call this set `S2`.
4.  Iterate through every subsequence `sub1` in `S1`.
5.  For each `sub1`, iterate through every subsequence `sub2` in `S2`.
6.  Construct the string `s = sub1 + sub2`.
7.  Check if `s` is a palindrome. A simple way to do this is to see if `s` is equal to its reverse.
8.  If `s` is a palindrome, update `maxLength = max(maxLength, s.length())`.
9.  After checking all pairs, return `maxLength`.

Generating all subsequences can be done with a recursive (backtracking) helper function.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int longestPalindrome(String word1, String word2) {
        List<String> subsequences1 = new ArrayList<>();
        generateSubsequences(word1, 0, "", subsequences1);

        List<String> subsequences2 = new ArrayList<>();
        generateSubsequences(word2, 0, "", subsequences2);

        int maxLength = 0;
        for (String sub1 : subsequences1) {
            for (String sub2 : subsequences2) {
                String combined = sub1 + sub2;
                if (isPalindrome(combined)) {
                    maxLength = Math.max(maxLength, combined.length());
                }
            }
        }
        return maxLength;
    }

    private void generateSubsequences(String s, int index, String current, List<String> result) {
        if (index == s.length()) {
            if (!current.isEmpty()) {
                result.add(current);
            }
            return;
        }
        // Exclude character at index
        generateSubsequences(s, index + 1, current, result);
        // Include character at index
        generateSubsequences(s, index + 1, current + s.charAt(index), result);
    }

    private boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}
```
### Algorithm
string

## Dynamic Programming on Combined String
A more efficient approach uses dynamic programming. The core idea is to find the longest palindromic subsequence that is specifically formed by characters from both `word1` and `word2`. We can simplify the problem by first concatenating the two strings, `s = word1 + word2`. Any palindrome we construct will be a subsequence of `s`.

The crucial insight is that the palindrome must be formed by a pair of matching characters, one from `word1` and one from `word2`, serving as the outer boundaries. The inner part of the palindrome would then be the longest palindromic subsequence of the string segment between these two characters. By pre-calculating the lengths of all possible longest palindromic subsequences within `s`, we can efficiently find the answer.
**Time:** O((n+m)^2) · **Space:** O((n+m)^2)
**Pros:** Efficient enough to solve the problem within the given constraints.; It's a standard dynamic programming pattern that can be adapted to similar problems.; Correctly models the problem by ensuring the constructed palindrome is a valid subsequence of the combined string, with the split point handled by the search loop.
**Cons:** Requires O((n+m)^2) space, which can be large for the maximum input size (e.g., 2000x2000 table).
### Explanation
The algorithm is as follows:

1.  Create a new string `s` by concatenating `word1` and `word2`. Let `n` be the length of `word1` and `N` be the length of `s`.
2.  Create a 2D DP table, `dp[N][N]`, where `dp[i][j]` will store the length of the longest palindromic subsequence (LPS) of the substring `s[i...j]`.
3.  Fill the `dp` table using the standard LPS algorithm. We iterate through substring lengths, and for each substring `s[i...j]`:
    *   If `s.charAt(i) == s.charAt(j)`, `dp[i][j] = 2 + dp[i+1][j-1]` (or `1` if `i==j`).
    *   If `s.charAt(i) != s.charAt(j)`, `dp[i][j] = max(dp[i+1][j], dp[i][j-1])`.
4.  Initialize `maxLength = 0`.
5.  Iterate through all possible starting characters from `word1` (index `i` from `0` to `n-1`) and ending characters from `word2` (index `k` in `word2`, which corresponds to index `j = n+k` in `s`).
6.  If `word1.charAt(i) == word2.charAt(k)`, we have found a potential pair for the palindrome's edges.
7.  The total length of the palindrome formed by this pair is `2` (for the pair itself) plus the length of the LPS of the middle part, `s[i+1...j-1]`. This value is already computed as `dp[i+1][j-1]`.
8.  Update `maxLength = max(maxLength, 2 + dp[i+1][j-1])`.
9.  If no common characters are found between `word1` and `word2`, `maxLength` will remain `0`, which is the correct result.

```java
class Solution {
    public int longestPalindrome(String word1, String word2) {
        String s = word1 + word2;
        int N = s.length();
        int n1 = word1.length();
        int[][] dp = new int[N][N];

        // Step 1: Compute the LPS table for the combined string s
        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)) {
                    // If j=i+1, dp[i+1][j-1] is dp[i+1][i] which is 0.
                    dp[i][j] = 2 + dp[i + 1][j - 1];
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }

        // Step 2: Find the max length for palindromes straddling word1 and word2
        int maxLength = 0;
        for (int i = 0; i < n1; i++) {
            // The corresponding character must be in word2
            // The indices for word2 in s are from n1 to N-1
            for (int j = n1; j < N; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    // The middle part is s[i+1...j-1]. Its LPS length is dp[i+1][j-1].
                    // If i+1 > j-1, the middle part is empty, and dp[i+1][j-1] will be 0.
                    int currentLength = 2 + dp[i + 1][j - 1];
                    maxLength = Math.max(maxLength, currentLength);
                }
            }
        }

        return maxLength;
    }
}
```
### Algorithm
string

# Solutions
### Java

```java
class Solution {
public
  int longestPalindrome(String word1, String word2) {
    String s = word1 + word2;
    int n = s.length();
    int[][] f = new int[n][n];
    for (int i = 0; i < n; ++i) {
      f[i][i] = 1;
    }
    int ans = 0;
    for (int i = n - 2; i >= 0; --i) {
      for (int j = i + 1; j < n; ++j) {
        if (s.charAt(i) == s.charAt(j)) {
          f[i][j] = f[i + 1][j - 1] + 2;
          if (i < word1.length() && j >= word1.length()) {
            ans = Math.max(ans, f[i][j]);
          }
        } else {
          f[i][j] = Math.max(f[i + 1][j], f[i][j - 1]);
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int longestPalindrome(string word1, string word2) {
    string s = word1 + word2;
    int n = s.size();
    int f[n][n];
    memset(f, 0, sizeof f);
    for (int i = 0; i < n; ++i)
      f[i][i] = 1;
    int ans = 0;
    for (int i = n - 2; ~i; --i) {
      for (int j = i + 1; j < n; ++j) {
        if (s[i] == s[j]) {
          f[i][j] = f[i + 1][j - 1] + 2;
          if (i < word1.size() && j >= word1.size()) {
            ans = max(ans, f[i][j]);
          }
        } else {
          f[i][j] = max(f[i + 1][j], f[i][j - 1]);
        }
      }
    }
    return ans;
  }
};

```

### Python

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

```