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 _thelength 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.

Examples

Example 1

1
2
3

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

1
2
3

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

1
2
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

Method 1 – Dynamic Programming with Split Point

Intuition

To maximize the palindrome length, we want to build a palindrome that uses at least one character from both word1 and word2. We concatenate the words and use dynamic programming to find the longest palindromic subsequence, ensuring that the palindrome includes at least one character from each word (i.e., the palindrome starts in word1 and ends in word2, or vice versa).

Approach

  1. Concatenate word1 and word2 to form s.
  2. Use DP to compute the longest palindromic subsequence for all substrings of s.
  3. For every pair (i, j) where i is in word1 and j is in word2 and s[i] == s[j], try to build a palindrome with s[i] and s[j] as the two ends, and the middle part is the longest palindromic subsequence between i+1 and j-1.
  4. Track the maximum length found.
  5. Return the maximum length.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    int longestPalindrome(string word1, string word2) {
        string s = word1 + word2;
        int n = s.size(), n1 = word1.size();
        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] = dp[i+1][j-1] + 2;
                else dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
            }
        }
        int ans = 0;
        for (int i = 0; i < n1; ++i) {
            for (int j = n1; j < n; ++j) {
                if (s[i] == s[j]) {
                    ans = max(ans, dp[i][j]);
                }
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

func longestPalindrome(word1 string, word2 string) int {
    s := word1 + word2
    n, n1 := len(s), len(word1)
    dp := make([][]int, n)
    for i := range dp {
        dp[i] = make([]int, n)
    }
    for i := n-1; i >= 0; i-- {
        dp[i][i] = 1
        for j := i+1; j < n; j++ {
            if s[i] == s[j] {
                if i+1 <= j-1 {
                    dp[i][j] = dp[i+1][j-1] + 2
                } else {
                    dp[i][j] = 2
                }
            } else {
                if dp[i+1][j] > dp[i][j-1] {
                    dp[i][j] = dp[i+1][j]
                } else {
                    dp[i][j] = dp[i][j-1]
                }
            }
        }
    }
    ans := 0
    for i := 0; i < n1; i++ {
        for j := n1; j < n; j++ {
            if s[i] == s[j] && dp[i][j] > ans {
                ans = dp[i][j]
            }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    public int longestPalindrome(String word1, String word2) {
        String s = word1 + word2;
        int n = s.length(), n1 = word1.length();
        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] = dp[i+1][j-1] + 2;
                else dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
            }
        }
        int ans = 0;
        for (int i = 0; i < n1; i++) {
            for (int j = n1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    ans = Math.max(ans, dp[i][j]);
                }
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    fun longestPalindrome(word1: String, word2: String): Int {
        val s = word1 + word2
        val n = s.length
        val n1 = word1.length
        val dp = Array(n) { IntArray(n) }
        for (i in n-1 downTo 0) {
            dp[i][i] = 1
            for (j in i+1 until n) {
                if (s[i] == s[j]) dp[i][j] = dp[i+1][j-1] + 2
                else dp[i][j] = maxOf(dp[i+1][j], dp[i][j-1])
            }
        }
        var ans = 0
        for (i in 0 until n1) {
            for (j in n1 until n) {
                if (s[i] == s[j]) {
                    ans = maxOf(ans, dp[i][j])
                }
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def longestPalindrome(self, word1: str, word2: str) -> int:
        s = word1 + word2
        n, n1 = len(s), len(word1)
        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] = dp[i+1][j-1] + 2
                else:
                    dp[i][j] = max(dp[i+1][j], dp[i][j-1])
        ans = 0
        for i in range(n1):
            for j in range(n1, n):
                if s[i] == s[j]:
                    ans = max(ans, dp[i][j])
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

impl Solution {
    pub fn longest_palindrome(word1: String, word2: String) -> i32 {
        let s = format!("{}{}", word1, word2);
        let n = s.len();
        let n1 = word1.len();
        let s = s.as_bytes();
        let mut dp = vec![vec![0; n]; n];
        for i in (0..n).rev() {
            dp[i][i] = 1;
            for j in i+1..n {
                if s[i] == s[j] {
                    dp[i][j] = dp[i+1][j-1] + 2;
                } else {
                    dp[i][j] = dp[i+1][j].max(dp[i][j-1]);
                }
            }
        }
        let mut ans = 0;
        for i in 0..n1 {
            for j in n1..n {
                if s[i] == s[j] {
                    ans = ans.max(dp[i][j]);
                }
            }
        }
        ans as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    longestPalindrome(word1: string, word2: string): number {
        const s = word1 + word2;
        const n = s.length, n1 = word1.length;
        const dp: number[][] = 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] = dp[i+1][j-1] + 2;
                else dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
            }
        }
        let ans = 0;
        for (let i = 0; i < n1; i++) {
            for (let j = n1; j < n; j++) {
                if (s[i] === s[j]) {
                    ans = Math.max(ans, dp[i][j]);
                }
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n^2) — for filling the DP table.
  • 🧺 Space complexity: O(n^2) — for the DP table.