Longest palindrome after substring concatenation ii

Two Pointers String Dynamic Programming

17.7% acceptance

Feb 25, 2026

You are given two strings, s and t. You can create a new string by selecting a substring from s (possibly empty) and a substring from t (possibly empty), then concatenating them in order. Return the length of the longest palindrome that can be formed this way.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn longest_palindrome(s: String, t: String) -> i32 {
    let sv: Vec<u8> = s.bytes().collect();
    let tv: Vec<u8> = t.bytes().collect();
    let n = sv.len();
    let m = tv.len();
    let rt: Vec<u8> = tv.iter().rev().copied().collect(); // reverse of t

    // Precompute max palindrome starting at each position for sv and rt
    let mps_s = max_pal_start(&sv);
    let mps_rt = max_pal_start(&rt);

    // lcp[i][j] = LCP of sv[i..] and rt[j..]
    let mut lcp = vec![vec![0usize; m + 1]; n + 1];
    for i in (0..n).rev() {
      for j in (0..m).rev() {
        if sv[i] == rt[j] {
          lcp[i][j] = lcp[i + 1][j + 1] + 1;
        }
      }
    }

    let mut best = 1i32;

    // Best palindrome entirely in s
    for i in 0..n {
      if mps_s[i] > best { best = mps_s[i]; }
    }
    // Best palindrome entirely in t (using rt palindromes)
    for i in 0..m {
      if mps_rt[i] > best { best = mps_rt[i]; }
    }

    // Cross-string palindromes
    for i in 0..n {
      for j in 0..m {
        let l = lcp[i][j];
        if l == 0 { continue; }
        let base = 2 * l as i32;
        best = best.max(base);
        // Center extension from s side
        let cs = if i + l <= n { mps_s[i + l] } else { 0 };
        best = best.max(base + cs);
        // Center extension from rt side
        let cr = if j + l <= m { mps_rt[j + l] } else { 0 };
        best = best.max(base + cr);
      }
    }

    best
  }
}

// max_pal_start[i] = max length of palindrome starting at index i in v
fn max_pal_start(v: &[u8]) -> Vec<i32> {
  let n = v.len();
  let mut res = vec![0i32; n + 1];
  if n == 0 { return res; }

  // Precompute is_pal[i][j]
  let mut dp = vec![vec![false; n]; n];
  for i in 0..n { dp[i][i] = true; res[i] = res[i].max(1); }
  for i in 0..n.saturating_sub(1) {
    if v[i] == v[i + 1] {
      dp[i][i + 1] = true;
      res[i] = res[i].max(2);
    }
  }
  for len in 3..=n {
    for i in 0..=n - len {
      let j = i + len - 1;
      if v[i] == v[j] && dp[i + 1][j - 1] {
        dp[i][j] = true;
        res[i] = res[i].max(len as i32);
      }
    }
  }
  res
}