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 <= 30
  • s and t consist of lowercase English letters.

Examples

Solution

Method 1 – Two Pointers and Center Expansion (1)

Intuition

To form the longest palindrome by concatenating a substring from s and a substring from t, we can try all possible splits and check for palindromes centered at the junction. The palindrome can be centered at the end of s and start of t, or fully within one string.

Approach

  1. For each possible split (i, j), where we take s[0:i] and t[j:], concatenate and check for the longest palindrome centered at the junction.
  2. Use center expansion to check for palindromes that cross the boundary between s and t.
  3. Also check for palindromes fully within s or t.
  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
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class Solution {
public:
    int longestPalindrome(string s, string t) {
        int n = s.size(), m = t.size(), ans = 0;
        string u = s + t;
        auto is_pal = [&](int l, int r) {
            while (l < r) if (u[l++] != u[r--]) return false;
            return true;
        };
        // Palindrome crossing the boundary
        for (int i = 0; i <= n; ++i) {
            for (int j = 0; j <= m; ++j) {
                int l = i-1, r = n+j;
                while (l >= 0 && r < n+m && u[l] == u[r]) {
                    l--; r++;
                }
                ans = max(ans, r-l-1);
            }
        }
        // Palindrome within s or t
        for (int i = 0; i < n+m; ++i) {
            int l = i, r = i;
            while (l >= 0 && r < n+m && u[l] == u[r]) {
                if ((l < n && r >= n) || (l >= n && r < n)) ans = max(ans, r-l+1);
                l--; r++;
            }
            l = i; r = i+1;
            while (l >= 0 && r < n+m && 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
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution:
    def longestPalindrome(self, s: str, t: str) -> int:
        n, m = len(s), len(t)
        u = s + t
        ans = 0
        # Palindrome crossing the boundary
        for i in range(n+1):
            for j in range(m+1):
                l, r = i-1, n+j
                while l >= 0 and r < n+m and u[l] == u[r]:
                    l -= 1
                    r += 1
                ans = max(ans, r-l-1)
        # Palindrome within s or t
        for i in range(n+m):
            l = r = i
            while l >= 0 and r < n+m 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
            l, r = i, i+1
            while l >= 0 and r < n+m 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.