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.

Example 1

1
2
3
4
5

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

1
2
3
4
5

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

1
2
3
4

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

Example 4

1
2
3
4
5

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.

Examples

Solution

Method 1 – Dynamic Programming with Center Expansion (1)

Intuition

To form the longest palindrome by concatenating a substring from s and a substring from t (possibly empty), we can try all possible splits and check for palindromes that cross the boundary. We use dynamic programming to check for palindromes efficiently.

Approach

  1. Concatenate s and t into a single string u.
  2. For each possible center (odd and even), expand around the center and check if the palindrome includes at least one character from both s and t.
  3. Track the maximum length of such palindromes.
  4. Return the maximum length found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int longestPalindrome(string s, string t) {
        string u = s + t;
        int n = s.size(), m = t.size(), ans = 0, N = n + m;
        for (int c = 0; c < N; ++c) {
            for (int d = 0; d < 2; ++d) {
                int l = c, r = c + d;
                while (l >= 0 && r < N && u[l] == u[r]) {
                    if ((l < n && r >= n) || (l >= n && r < n))
                        ans = max(ans, r - l + 1);
                    l--; r++;
                }
            }
        }
        return ans;
    }
};
1

// Omitted for brevity. See Python for main logic.
1

// Omitted for brevity. See Python for main logic.
1

// Omitted for brevity. See Python for main logic.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def longestPalindrome(self, s: str, t: str) -> int:
        u = s + t
        n, m = len(s), len(t)
        ans = 0
        N = n + m
        for c in range(N):
            for d in range(2):
                l, r = c, c + d
                while l >= 0 and r < N and u[l] == u[r]:
                    if (l < n and r >= n) or (l >= n and r < n):
                        ans = max(ans, r - l + 1)
                    l -= 1
                    r += 1
        return ans
1

// Omitted for brevity. See Python for main logic.

1

// Omitted for brevity. See Python for main logic.

Complexity

  • ⏰ Time complexity: O((n+m)^2), where n and m are the lengths of s and t. We check all centers.
  • 🧺 Space complexity: O(n+m), for the concatenated string.