Maximize palindrome length from subsequences

String Dynamic Programming

38.2% acceptance

Feb 25, 2026

566

You are given two strings, word1 and word2. You want to construct a string by choosing some non-empty subsequence from word1 and some non-empty subsequence from word2, then concatenating them. Return the length of the longest palindrome that can be constructed in the described manner. If no palindromes can be constructed, return 0.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn longest_palindrome(word1: String, word2: String) -> i32 {
    let n1 = word1.len();
    let s = (word1 + &word2).into_bytes();
    let n = s.len();
    // dp[i][j] = length of longest palindromic subsequence in s[i..=j]
    let mut dp = vec![vec![0i32; n]; n];
    for i in 0..n { dp[i][i] = 1; }
    for len in 2..=n {
      for i in 0..=n-len {
        let j = i + len - 1;
        if s[i] == s[j] {
          dp[i][j] = if len == 2 { 2 } else { dp[i+1][j-1] + 2 };
        } else {
          dp[i][j] = dp[i+1][j].max(dp[i][j-1]);
        }
      }
    }
    // Answer: max dp[i][j] where i < n1 and j >= n1 and s[i] == s[j]
    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
  }
}