Longest palindrome after substring concatenation i

Two Pointers String Dynamic Programming Enumeration

43.8% 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³)

Space O(1)

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 is_pal = |v: &[u8]| -> bool {
      let l = v.len();
      (0..l / 2).all(|i| v[i] == v[l - 1 - i])
    };

    let mut best = 1i32;
    // Try all pairs of substrings (including empty)
    for si in 0..=n {
      for sj in si..=n {
        for ti in 0..=m {
          for tj in ti..=m {
            if si == sj && ti == tj { continue; }
            let combined: Vec<u8> = sv[si..sj].iter().chain(tv[ti..tj].iter()).copied().collect();
            if !combined.is_empty() && is_pal(&combined) {
              best = best.max(combined.len() as i32);
            }
          }
        }
      }
    }
    best
  }
}