Longest Palindrome After Substring Concatenation I
MediumUpdated: Aug 7, 2025
Practice on:
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 <= 30sandtconsist of lowercase English letters.
Solution
Method 1 – Two Pointers and Center Expansion
Intuition
To find the longest palindrome by concatenating substrings from s and t, we need to consider all possible ways to take a prefix from s and a suffix from t. For each such concatenation, we find the longest palindrome within that string using center expansion technique.
Approach
-
Generate all possible concatenations: For each possible prefix length
ifroms(0 to m) and suffix starting positionjfromt(0 to n), create the concatenated strings[0:i] + t[j:n]. -
Find longest palindrome in each concatenation: For each concatenated string, use the center expansion technique to find the longest palindrome:
- Check for odd-length palindromes (center at single character)
- Check for even-length palindromes (center between two characters)
-
Center expansion: For each potential center, expand outward while characters match, keeping track of the maximum palindrome length found.
-
Return maximum: Track and return the maximum palindrome length across all possible concatenations.
Code
C++
class Solution {
public:
int longestPalindrome(string s, string t) {
int m = s.length(), n = t.length(), maxLen = 0;
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
string concat = s.substr(0, i) + t.substr(j);
int len = concat.length();
for (int k = 0; k < len; k++) {
// Check odd-length palindromes (center at k)
maxLen = max(maxLen, expandAroundCenter(concat, k, k));
// Check even-length palindromes (center between k and k+1)
maxLen = max(maxLen, expandAroundCenter(concat, k, k + 1));
}
}
}
return maxLen;
}
private:
int expandAroundCenter(const string& str, int left, int right) {
while (left >= 0 && right < str.length() && str[left] == str[right]) {
left--;
right++;
}
return right - left - 1;
}
};
Go
func longestPalindrome(s string, t string) int {
m, n := len(s), len(t)
maxLen := 0
for i := 0; i <= m; i++ {
for j := 0; j <= n; j++ {
concat := s[:i] + t[j:]
length := len(concat)
for k := 0; k < length; k++ {
// Check odd-length palindromes
maxLen = max(maxLen, expandAroundCenter(concat, k, k))
// Check even-length palindromes
maxLen = max(maxLen, expandAroundCenter(concat, k, k+1))
}
}
}
return maxLen
}
func expandAroundCenter(str string, left, right int) int {
for left >= 0 && right < len(str) && str[left] == str[right] {
left--
right++
}
return right - left - 1
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
Java
class Solution {
public int longestPalindrome(String s, String t) {
int m = s.length(), n = t.length(), maxLen = 0;
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
String concat = s.substring(0, i) + t.substring(j);
int length = concat.length();
for (int k = 0; k < length; k++) {
// Check odd-length palindromes
maxLen = Math.max(maxLen, expandAroundCenter(concat, k, k));
// Check even-length palindromes
maxLen = Math.max(maxLen, expandAroundCenter(concat, k, k + 1));
}
}
}
return maxLen;
}
private int expandAroundCenter(String str, int left, int right) {
while (left >= 0 && right < str.length() && str.charAt(left) == str.charAt(right)) {
left--;
right++;
}
return right - left - 1;
}
}
Kotlin
class Solution {
fun longestPalindrome(s: String, t: String): Int {
val m = s.length
val n = t.length
var maxLen = 0
for (i in 0..m) {
for (j in 0..n) {
val concat = s.substring(0, i) + t.substring(j)
val length = concat.length
for (k in 0 until length) {
// Check odd-length palindromes
maxLen = maxOf(maxLen, expandAroundCenter(concat, k, k))
// Check even-length palindromes
maxLen = maxOf(maxLen, expandAroundCenter(concat, k, k + 1))
}
}
}
return maxLen
}
private fun expandAroundCenter(str: String, left: Int, right: Int): Int {
var l = left
var r = right
while (l >= 0 && r < str.length && str[l] == str[r]) {
l--
r++
}
return r - l - 1
}
}
Python
class Solution:
def longestPalindrome(self, s: str, t: str) -> int:
m, n = len(s), len(t)
max_len = 0
for i in range(m + 1):
for j in range(n + 1):
concat = s[:i] + t[j:]
length = len(concat)
for k in range(length):
# Check odd-length palindromes
max_len = max(max_len, self.expand_around_center(concat, k, k))
# Check even-length palindromes
max_len = max(max_len, self.expand_around_center(concat, k, k + 1))
return max_len
def expand_around_center(self, s: str, left: int, right: int) -> int:
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return right - left - 1
Rust
impl Solution {
pub fn longest_palindrome(s: String, t: String) -> i32 {
let m = s.len();
let n = t.len();
let mut max_len = 0;
for i in 0..=m {
for j in 0..=n {
let concat = format!("{}{}", &s[..i], &t[j..]);
let chars: Vec<char> = concat.chars().collect();
let length = chars.len();
for k in 0..length {
// Check odd-length palindromes
max_len = max_len.max(Self::expand_around_center(&chars, k, k));
// Check even-length palindromes
if k + 1 < length {
max_len = max_len.max(Self::expand_around_center(&chars, k, k + 1));
}
}
}
}
max_len as i32
}
fn expand_around_center(chars: &[char], mut left: usize, mut right: usize) -> usize {
while left < chars.len() && right < chars.len() && chars[left] == chars[right] {
if left == 0 {
break;
}
left -= 1;
right += 1;
}
if left < chars.len() && right < chars.len() && chars[left] == chars[right] {
right - left + 1
} else {
right - left - 1
}
}
}
TypeScript
function longestPalindrome(s: string, t: string): number {
const m = s.length;
const n = t.length;
let maxLen = 0;
for (let i = 0; i <= m; i++) {
for (let j = 0; j <= n; j++) {
const concat = s.substring(0, i) + t.substring(j);
const length = concat.length;
for (let k = 0; k < length; k++) {
// Check odd-length palindromes
maxLen = Math.max(maxLen, expandAroundCenter(concat, k, k));
// Check even-length palindromes
maxLen = Math.max(maxLen, expandAroundCenter(concat, k, k + 1));
}
}
}
return maxLen;
}
function expandAroundCenter(str: string, left: number, right: number): number {
while (left >= 0 && right < str.length && str[left] === str[right]) {
left--;
right++;
}
return right - left - 1;
}
Complexity
- ⏰ Time complexity:
O(n*m*(n+m)^2), where n and m are the lengths of s and t. We generateO(n*m)possible concatenations (each prefix of s with each suffix of t). For each concatenation of length up to(n+m), we checkO(n+m)possible centers, and each center expansion takesO(n+m)time in the worst case. - 🧺 Space complexity:
O(n+m), for storing the concatenated strings during processing.