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

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.

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

  1. Generate all possible concatenations: For each possible prefix length i from s (0 to m) and suffix starting position j from t (0 to n), create the concatenated string s[0:i] + t[j:n].

  2. 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)

  3. Center expansion: For each potential center, expand outward while characters match, keeping track of the maximum palindrome length found.

  4. Return maximum: Track and return the maximum palindrome length across all possible concatenations.

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

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;
    }
};
 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

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
}
 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

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;
    }
}
 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

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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
 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
36
37
38
39
40
41
42

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
        }
    }
}
 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

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 generate O(n*m) possible concatenations (each prefix of s with each suffix of t). For each concatenation of length up to (n+m), we check O(n+m) possible centers, and each center expansion takes O(n+m) time in the worst case.
  • 🧺 Space complexity: O(n+m), for storing the concatenated strings during processing.