3504. Longest Palindrome After Substring Concatenation II LeetCode Solution

Last updated: April 1, 2025

In this guide, you will get 3504. Longest Palindrome After Substring Concatenation II LeetCode Solution with the best time and space complexity. The solution to Longest Palindrome After Substring Concatenation II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Longest Palindrome After Substring Concatenation II solution in C++
Longest Palindrome After Substring Concatenation II solution in Java
Longest Palindrome After Substring Concatenation II solution in Python
Additional Resources

3504. Longest Palindrome After Substring Concatenation II LeetCode Solution image

Problem Statement of Longest Palindrome After Substring Concatenation II

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:

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.

Complexity Analysis

Time Complexity: O(|\texttt{s}||\texttt{t}|)
Space Complexity: O(|\texttt{s}||\texttt{t}|)

3504. Longest Palindrome After Substring Concatenation II LeetCode Solution in C++

class Solution:
  def longestPalindrome(self, s: str, t: str) -> int:
    m = len(s)
    n = len(t)
    suffix = self._getPalindromeLengths(s, True)
    prefix = self._getPalindromeLengths(t, False)
    ans = max(max(suffix), max(prefix))
    # dp[i][j] := the longest length of palindrome starting in s[i] and ending
    # in t[j]
    dp = [[0] * n for _ in range(m)]

    for i in range(m):
      for j in range(n - 1, -1, -1):
        if s[i] == t[j]:
          dp[i][j] = 2 + (dp[i - 1][j + 1] if i > 0 and j < n - 1 else 0)
          extend = max(suffix[i + 1] if i + 1 < m else 0,
                       prefix[j - 1] if j > 0 else 0)
          ans = max(ans, dp[i][j] + extend)

    return ans

  def _getPalindromeLengths(self, s: str, isSuffix: bool) -> list[int]:
    n = len(s)
    # dp[i][j] := True if s[i..j] is a palindrome
    dp = [[False] * n for _ in range(n)]
    # lengths[i] := length of longest palindrome in s[i..n - 1]
    lengths = [0] * n
    for i in range(n - 1, -1, -1):
      for j in range(i, n):
        if s[i] == s[j] and (j - i < 2 or dp[i + 1][j - 1]):
          dp[i][j] = True
          index = i if isSuffix else j
          lengths[index] = max(lengths[index], j - i + 1)
    return lengths
/* code provided by PROGIEZ */

3504. Longest Palindrome After Substring Concatenation II LeetCode Solution in Java

N/A
// code provided by PROGIEZ

3504. Longest Palindrome After Substring Concatenation II LeetCode Solution in Python

N/A
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents