Longest Palindrome After Substring Concatenation II

Problem

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.

Examples

Example 1

Input: s = "a", t = "a"
Output: 2
Explanation:
Concatenating `"a"` from `s` and `"a"` from `t` results in `"aa"`, which is a
palindrome of length 2.

Example 2

Input: s = "abc", t = "def"
Output: 1
Explanation:
Since all characters are different, the longest palindrome is any single
character, so the answer is 1.

Example 3

Input: s = "b", t = "aaaa"
Output: 4
Explanation:
Selecting "`aaaa`" from `t` is the longest palindrome, so the answer is 4.

Example 4

Input: s = "abcde", t = "ecdba"
Output: 5
Explanation:
Concatenating `"abc"` from `s` and `"ba"` from `t` results in `"abcba"`, which
is a palindrome of length 5.

Constraints

• 1 <= s.length, t.length <= 1000
• s and t consist of lowercase English letters.

Solution

Method 1 – Dynamic Programming with Center Expansion

Intuition

To find the longest palindrome by concatenating substrings from s and t, we need to consider several possible cases:

1. Palindromic substring from s only: Take any palindromic substring from s and empty substring from t
2. Palindromic substring from t only: Take empty substring from s and any palindromic substring from t
3. Palindromic combination crossing both strings: Take a suffix from s and a prefix from t that together form a palindrome (e.g., "ab" from s + "ba" from t)
4. Extended palindromic combination: A palindromic combination from case 3, extended with additional palindromic substrings from either end

The key insight is to precompute the longest palindromic substrings for efficient lookup and use dynamic programming to explore palindromic combinations that span both strings.

Approach

1. Precompute palindromic information:

   • For string s: Create dps[i] = longest palindromic substring starting at index i
   • For string t: Create dpt[i] = longest palindromic substring ending at index i

2. Initialize answer with single-string palindromes: Track the maximum palindrome length from s or t alone

3. Dynamic Programming for cross-string palindromes:

   • Start from the middle of both strings and work outward
   • Use DP to find palindromic combinations where characters from s match characters from t
   • For each matching pair, extend the palindrome and combine with precomputed palindromic substrings

4. Optimize with memoization: Cache results to avoid redundant computations and achieve better time complexity

Code

C++

class Solution {
private:
    int ans;
    vector<vector<int>> memo;
    
    vector<int> lpsStart(const string& s) {
        int n = s.length();
        vector<int> res(n, 1);
        
        for (int i = 0; i < n; i++) {
            // Odd length palindromes
            int len = expand(s, i, i);
            if (i - len >= 0) {
                res[i - len] = max(res[i - len], len * 2 + 1);
            }
            
            // Even length palindromes
            len = expand(s, i, i + 1);
            if (len >= 0 && i - len >= 0) {
                res[i - len] = max(res[i - len], len * 2 + 2);
            }
        }
        return res;
    }
    
    vector<int> lpsEnd(const string& s) {
        int n = s.length();
        vector<int> res(n, 1);
        
        for (int i = 0; i < n; i++) {
            // Odd length palindromes
            int len = expand(s, i, i);
            if (i + len < n) {
                res[i + len] = max(res[i + len], len * 2 + 1);
            }
            
            // Even length palindromes
            len = expand(s, i - 1, i);
            if (len >= 0 && i + len < n) {
                res[i + len] = max(res[i + len], len * 2 + 2);
            }
        }
        return res;
    }
    
    int expand(const string& s, int l, int r) {
        int res = 0;
        while (l >= 0 && r < s.length() && s[l] == s[r]) {
            res++;
            l--;
            r++;
        }
        return res - 1;
    }
    
    int find(const vector<int>& dps, const vector<int>& dpt, 
             const string& s, const string& t, int i, int j) {
        if (i < 0 || j >= t.length()) return 0;
        if (memo[i][j] != -1) return memo[i][j];
        
        int res = 0;
        if (s[i] == t[j]) {
            res = 2 + find(dps, dpt, s, t, i - 1, j + 1);
        }
        
        // Update answer with current palindrome + extensions
        ans = max(ans, res + (j > 0 ? dpt[j - 1] : 0));
        ans = max(ans, res + (i < s.length() - 1 ? dps[i + 1] : 0));
        
        // Continue exploring
        find(dps, dpt, s, t, i - 1, j);
        find(dps, dpt, s, t, i, j + 1);
        
        return memo[i][j] = res;
    }
    
public:
    int longestPalindrome(string s, string t) {
        ans = 0;
        memo.assign(s.length(), vector<int>(t.length(), -1));
        
        vector<int> dps = lpsStart(s);
        vector<int> dpt = lpsEnd(t);
        
        // Check single string palindromes
        for (int len : dps) ans = max(ans, len);
        for (int len : dpt) ans = max(ans, len);
        
        // Find cross-string palindromes
        find(dps, dpt, s, t, s.length() - 1, 0);
        
        return ans;
    }
};

Go

var ans int
var memo [][]int

func longestPalindrome(s string, t string) int {
    ans = 0
    memo = make([][]int, len(s))
    for i := range memo {
        memo[i] = make([]int, len(t))
        for j := range memo[i] {
            memo[i][j] = -1
        }
    }
    
    dps := lpsStart(s)
    dpt := lpsEnd(t)
    
    // Check single string palindromes
    for _, length := range dps {
        ans = max(ans, length)
    }
    for _, length := range dpt {
        ans = max(ans, length)
    }
    
    // Find cross-string palindromes
    find(dps, dpt, s, t, len(s)-1, 0)
    
    return ans
}

func lpsStart(s string) []int {
    n := len(s)
    res := make([]int, n)
    for i := range res {
        res[i] = 1
    }
    
    for i := 0; i < n; i++ {
        // Odd length palindromes
        length := expand(s, i, i)
        if i-length >= 0 {
            res[i-length] = max(res[i-length], length*2+1)
        }
        
        // Even length palindromes
        length = expand(s, i, i+1)
        if length >= 0 && i-length >= 0 {
            res[i-length] = max(res[i-length], length*2+2)
        }
    }
    return res
}

func lpsEnd(s string) []int {
    n := len(s)
    res := make([]int, n)
    for i := range res {
        res[i] = 1
    }
    
    for i := 0; i < n; i++ {
        // Odd length palindromes
        length := expand(s, i, i)
        if i+length < n {
            res[i+length] = max(res[i+length], length*2+1)
        }
        
        // Even length palindromes
        length = expand(s, i-1, i)
        if length >= 0 && i+length < n {
            res[i+length] = max(res[i+length], length*2+2)
        }
    }
    return res
}

func expand(s string, l, r int) int {
    res := 0
    for l >= 0 && r < len(s) && s[l] == s[r] {
        res++
        l--
        r++
    }
    return res - 1
}

func find(dps, dpt []int, s, t string, i, j int) int {
    if i < 0 || j >= len(t) {
        return 0
    }
    if memo[i][j] != -1 {
        return memo[i][j]
    }
    
    res := 0
    if s[i] == t[j] {
        res = 2 + find(dps, dpt, s, t, i-1, j+1)
    }
    
    // Update answer with current palindrome + extensions
    if j > 0 {
        ans = max(ans, res+dpt[j-1])
    } else {
        ans = max(ans, res)
    }
    if i < len(s)-1 {
        ans = max(ans, res+dps[i+1])
    } else {
        ans = max(ans, res)
    }
    
    // Continue exploring
    find(dps, dpt, s, t, i-1, j)
    find(dps, dpt, s, t, i, j+1)
    
    memo[i][j] = res
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Java

class Solution {
    private int ans;
    private Integer[][] memo;
    
    public int longestPalindrome(String s, String t) {
        ans = 0;
        memo = new Integer[s.length()][t.length()];
        
        int[] dps = lpsStart(s);
        int[] dpt = lpsEnd(t);
        
        // Check single string palindromes
        for (int length : dps) {
            ans = Math.max(ans, length);
        }
        for (int length : dpt) {
            ans = Math.max(ans, length);
        }
        
        // Find cross-string palindromes
        find(dps, dpt, s, t, s.length() - 1, 0);
        
        return ans;
    }
    
    private int[] lpsStart(String s) {
        int n = s.length();
        int[] res = new int[n];
        Arrays.fill(res, 1);
        
        for (int i = 0; i < n; i++) {
            // Odd length palindromes
            int len = expand(s, i, i);
            if (i - len >= 0) {
                res[i - len] = Math.max(res[i - len], len * 2 + 1);
            }
            
            // Even length palindromes
            len = expand(s, i, i + 1);
            if (len >= 0 && i - len >= 0) {
                res[i - len] = Math.max(res[i - len], len * 2 + 2);
            }
        }
        return res;
    }
    
    private int[] lpsEnd(String s) {
        int n = s.length();
        int[] res = new int[n];
        Arrays.fill(res, 1);
        
        for (int i = 0; i < n; i++) {
            // Odd length palindromes
            int len = expand(s, i, i);
            if (i + len < n) {
                res[i + len] = Math.max(res[i + len], len * 2 + 1);
            }
            
            // Even length palindromes
            len = expand(s, i - 1, i);
            if (len >= 0 && i + len < n) {
                res[i + len] = Math.max(res[i + len], len * 2 + 2);
            }
        }
        return res;
    }
    
    private int expand(String s, int l, int r) {
        int res = 0;
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            res++;
            l--;
            r++;
        }
        return res - 1;
    }
    
    private int find(int[] dps, int[] dpt, String s, String t, int i, int j) {
        if (i < 0 || j >= t.length()) return 0;
        if (memo[i][j] != null) return memo[i][j];
        
        int res = 0;
        if (s.charAt(i) == t.charAt(j)) {
            res = 2 + find(dps, dpt, s, t, i - 1, j + 1);
        }
        
        // Update answer with current palindrome + extensions
        ans = Math.max(ans, res + (j > 0 ? dpt[j - 1] : 0));
        ans = Math.max(ans, res + (i < s.length() - 1 ? dps[i + 1] : 0));
        
        // Continue exploring
        find(dps, dpt, s, t, i - 1, j);
        find(dps, dpt, s, t, i, j + 1);
        
        return memo[i][j] = res;
    }
}

Kotlin

class Solution {
    private var ans = 0
    private lateinit var memo: Array<Array<Int?>>
    
    fun longestPalindrome(s: String, t: String): Int {
        ans = 0
        memo = Array(s.length) { Array<Int?>(t.length) { null } }
        
        val dps = lpsStart(s)
        val dpt = lpsEnd(t)
        
        // Check single string palindromes
        for (length in dps) {
            ans = maxOf(ans, length)
        }
        for (length in dpt) {
            ans = maxOf(ans, length)
        }
        
        // Find cross-string palindromes
        find(dps, dpt, s, t, s.length - 1, 0)
        
        return ans
    }
    
    private fun lpsStart(s: String): IntArray {
        val n = s.length
        val res = IntArray(n) { 1 }
        
        for (i in 0 until n) {
            // Odd length palindromes
            var len = expand(s, i, i)
            if (i - len >= 0) {
                res[i - len] = maxOf(res[i - len], len * 2 + 1)
            }
            
            // Even length palindromes
            len = expand(s, i, i + 1)
            if (len >= 0 && i - len >= 0) {
                res[i - len] = maxOf(res[i - len], len * 2 + 2)
            }
        }
        return res
    }
    
    private fun lpsEnd(s: String): IntArray {
        val n = s.length
        val res = IntArray(n) { 1 }
        
        for (i in 0 until n) {
            // Odd length palindromes
            var len = expand(s, i, i)
            if (i + len < n) {
                res[i + len] = maxOf(res[i + len], len * 2 + 1)
            }
            
            // Even length palindromes
            len = expand(s, i - 1, i)
            if (len >= 0 && i + len < n) {
                res[i + len] = maxOf(res[i + len], len * 2 + 2)
            }
        }
        return res
    }
    
    private fun expand(s: String, l: Int, r: Int): Int {
        var left = l
        var right = r
        var res = 0
        while (left >= 0 && right < s.length && s[left] == s[right]) {
            res++
            left--
            right++
        }
        return res - 1
    }
    
    private fun find(dps: IntArray, dpt: IntArray, s: String, t: String, i: Int, j: Int): Int {
        if (i < 0 || j >= t.length) return 0
        memo[i][j]?.let { return it }
        
        var res = 0
        if (s[i] == t[j]) {
            res = 2 + find(dps, dpt, s, t, i - 1, j + 1)
        }
        
        // Update answer with current palindrome + extensions
        ans = maxOf(ans, res + if (j > 0) dpt[j - 1] else 0)
        ans = maxOf(ans, res + if (i < s.length - 1) dps[i + 1] else 0)
        
        // Continue exploring
        find(dps, dpt, s, t, i - 1, j)
        find(dps, dpt, s, t, i, j + 1)
        
        memo[i][j] = res
        return res
    }
}

Python

class Solution:
    def longestPalindrome(self, s: str, t: str) -> int:
        self.ans = 0
        self.memo = {}
        
        dps = self.lps_start(s)
        dpt = self.lps_end(t)
        
        # Check single string palindromes
        for length in dps:
            self.ans = max(self.ans, length)
        for length in dpt:
            self.ans = max(self.ans, length)
        
        # Find cross-string palindromes
        self.find(dps, dpt, s, t, len(s) - 1, 0)
        
        return self.ans
    
    def lps_start(self, s: str) -> list[int]:
        n = len(s)
        res = [1] * n
        
        for i in range(n):
            # Odd length palindromes
            length = self.expand(s, i, i)
            if i - length >= 0:
                res[i - length] = max(res[i - length], length * 2 + 1)
            
            # Even length palindromes
            length = self.expand(s, i, i + 1)
            if length >= 0 and i - length >= 0:
                res[i - length] = max(res[i - length], length * 2 + 2)
        
        return res
    
    def lps_end(self, s: str) -> list[int]:
        n = len(s)
        res = [1] * n
        
        for i in range(n):
            # Odd length palindromes
            length = self.expand(s, i, i)
            if i + length < n:
                res[i + length] = max(res[i + length], length * 2 + 1)
            
            # Even length palindromes
            length = self.expand(s, i - 1, i)
            if length >= 0 and i + length < n:
                res[i + length] = max(res[i + length], length * 2 + 2)
        
        return res
    
    def expand(self, s: str, l: int, r: int) -> int:
        res = 0
        while l >= 0 and r < len(s) and s[l] == s[r]:
            res += 1
            l -= 1
            r += 1
        return res - 1
    
    def find(self, dps: list[int], dpt: list[int], s: str, t: str, i: int, j: int) -> int:
        if i < 0 or j >= len(t):
            return 0
        if (i, j) in self.memo:
            return self.memo[(i, j)]
        
        res = 0
        if s[i] == t[j]:
            res = 2 + self.find(dps, dpt, s, t, i - 1, j + 1)
        
        # Update answer with current palindrome + extensions
        self.ans = max(self.ans, res + (dpt[j - 1] if j > 0 else 0))
        self.ans = max(self.ans, res + (dps[i + 1] if i < len(s) - 1 else 0))
        
        # Continue exploring
        self.find(dps, dpt, s, t, i - 1, j)
        self.find(dps, dpt, s, t, i, j + 1)
        
        self.memo[(i, j)] = res
        return res

Rust

use std::collections::HashMap;

impl Solution {
    pub fn longest_palindrome(s: String, t: String) -> i32 {
        let mut ans = 0;
        let mut memo = HashMap::new();
        
        let dps = Self::lps_start(&s);
        let dpt = Self::lps_end(&t);
        
        // Check single string palindromes
        for &length in &dps {
            ans = ans.max(length);
        }
        for &length in &dpt {
            ans = ans.max(length);
        }
        
        // Find cross-string palindromes
        Self::find(&dps, &dpt, &s, &t, s.len() as i32 - 1, 0, &mut memo, &mut ans);
        
        ans
    }
    
    fn lps_start(s: &str) -> Vec<i32> {
        let n = s.len();
        let mut res = vec![1; n];
        let chars: Vec<char> = s.chars().collect();
        
        for i in 0..n {
            // Odd length palindromes
            let len = Self::expand(&chars, i as i32, i as i32);
            if i as i32 - len >= 0 {
                let idx = (i as i32 - len) as usize;
                res[idx] = res[idx].max(len * 2 + 1);
            }
            
            // Even length palindromes
            let len = Self::expand(&chars, i as i32, i as i32 + 1);
            if len >= 0 && i as i32 - len >= 0 {
                let idx = (i as i32 - len) as usize;
                res[idx] = res[idx].max(len * 2 + 2);
            }
        }
        res
    }
    
    fn lps_end(s: &str) -> Vec<i32> {
        let n = s.len();
        let mut res = vec![1; n];
        let chars: Vec<char> = s.chars().collect();
        
        for i in 0..n {
            // Odd length palindromes
            let len = Self::expand(&chars, i as i32, i as i32);
            if i + len as usize < n {
                let idx = i + len as usize;
                res[idx] = res[idx].max(len * 2 + 1);
            }
            
            // Even length palindromes
            let len = Self::expand(&chars, i as i32 - 1, i as i32);
            if len >= 0 && i + len as usize < n {
                let idx = i + len as usize;
                res[idx] = res[idx].max(len * 2 + 2);
            }
        }
        res
    }
    
    fn expand(chars: &[char], mut l: i32, mut r: i32) -> i32 {
        let mut res = 0;
        while l >= 0 && r < chars.len() as i32 && chars[l as usize] == chars[r as usize] {
            res += 1;
            l -= 1;
            r += 1;
        }
        res - 1
    }
    
    fn find(
        dps: &[i32], dpt: &[i32], s: &str, t: &str, i: i32, j: i32,
        memo: &mut HashMap<(i32, i32), i32>, ans: &mut i32
    ) -> i32 {
        if i < 0 || j >= t.len() as i32 {
            return 0;
        }
        if let Some(&cached) = memo.get(&(i, j)) {
            return cached;
        }
        
        let mut res = 0;
        let s_chars: Vec<char> = s.chars().collect();
        let t_chars: Vec<char> = t.chars().collect();
        
        if s_chars[i as usize] == t_chars[j as usize] {
            res = 2 + Self::find(dps, dpt, s, t, i - 1, j + 1, memo, ans);
        }
        
        // Update answer with current palindrome + extensions
        *ans = (*ans).max(res + if j > 0 { dpt[(j - 1) as usize] } else { 0 });
        *ans = (*ans).max(res + if i < s.len() as i32 - 1 { dps[(i + 1) as usize] } else { 0 });
        
        // Continue exploring
        Self::find(dps, dpt, s, t, i - 1, j, memo, ans);
        Self::find(dps, dpt, s, t, i, j + 1, memo, ans);
        
        memo.insert((i, j), res);
        res
    }
}

TypeScript

function longestPalindrome(s: string, t: string): number {
    let ans = 0;
    const memo = new Map<string, number>();
    
    const dps = lpsStart(s);
    const dpt = lpsEnd(t);
    
    // Check single string palindromes
    for (const length of dps) {
        ans = Math.max(ans, length);
    }
    for (const length of dpt) {
        ans = Math.max(ans, length);
    }
    
    // Find cross-string palindromes
    find(dps, dpt, s, t, s.length - 1, 0, memo, ans);
    
    return ans;
}

function lpsStart(s: string): number[] {
    const n = s.length;
    const res = new Array(n).fill(1);
    
    for (let i = 0; i < n; i++) {
        // Odd length palindromes
        let len = expand(s, i, i);
        if (i - len >= 0) {
            res[i - len] = Math.max(res[i - len], len * 2 + 1);
        }
        
        // Even length palindromes
        len = expand(s, i, i + 1);
        if (len >= 0 && i - len >= 0) {
            res[i - len] = Math.max(res[i - len], len * 2 + 2);
        }
    }
    return res;
}

function lpsEnd(s: string): number[] {
    const n = s.length;
    const res = new Array(n).fill(1);
    
    for (let i = 0; i < n; i++) {
        // Odd length palindromes
        let len = expand(s, i, i);
        if (i + len < n) {
            res[i + len] = Math.max(res[i + len], len * 2 + 1);
        }
        
        // Even length palindromes
        len = expand(s, i - 1, i);
        if (len >= 0 && i + len < n) {
            res[i + len] = Math.max(res[i + len], len * 2 + 2);
        }
    }
    return res;
}

function expand(s: string, l: number, r: number): number {
    let res = 0;
    while (l >= 0 && r < s.length && s[l] === s[r]) {
        res++;
        l--;
        r++;
    }
    return res - 1;
}

function find(
    dps: number[], dpt: number[], s: string, t: string, 
    i: number, j: number, memo: Map<string, number>, ans: number
): number {
    if (i < 0 || j >= t.length) return 0;
    
    const key = `${i},${j}`;
    if (memo.has(key)) return memo.get(key)!;
    
    let res = 0;
    if (s[i] === t[j]) {
        res = 2 + find(dps, dpt, s, t, i - 1, j + 1, memo, ans);
    }
    
    // Update answer with current palindrome + extensions
    ans = Math.max(ans, res + (j > 0 ? dpt[j - 1] : 0));
    ans = Math.max(ans, res + (i < s.length - 1 ? dps[i + 1] : 0));
    
    // Continue exploring
    find(dps, dpt, s, t, i - 1, j, memo, ans);
    find(dps, dpt, s, t, i, j + 1, memo, ans);
    
    memo.set(key, res);
    return res;
}

Complexity

• ⏰ Time complexity: O(max(n², m², n*m)), where n and m are the lengths of s and t. The preprocessing steps for computing LPS arrays take O(n²) and O(m²), while the DP exploration takes O(n*m) with memoization.
• 🧺 Space complexity: O(n*m), for the memoization table storing DP results.