LeetCode Problem 3504

Difficulty: 🔴 Hard
Topics: Two Pointers, String, Dynamic Programming

Solution

LeetCode 3504, Longest Palindrome After Substring Concatenation II

Problem Understanding

We are given two strings, s and t.

We may choose any substring from s and any substring from t. Either substring is allowed to be empty. After selecting them, we concatenate them in this exact order:

substring_from_s + substring_from_t

The resulting string must be a palindrome, and we want the maximum possible palindrome length.

A substring means a contiguous segment of characters. We are not allowed to skip characters as we could in a subsequence problem.

For example:

s = "abcde"
t = "ecdba"

Choosing:

"abc" from s
"ba"  from t

produces:

"abcba"

which is a palindrome of length 5.

The constraints are:

1 <= |s|, |t| <= 1000

This immediately rules out any approach that enumerates all substring pairs and explicitly checks every concatenation. Each string already has O(n²) substrings, so the total number of pairs becomes O(n⁴).

Several edge cases are important:

• The optimal palindrome may come entirely from s.
• The optimal palindrome may come entirely from t.
• One selected substring may be empty.
• The palindrome may have an odd-length center that lies completely inside s.
• The palindrome may have an odd-length center that lies completely inside t.
• The two strings may share no matching characters, in which case the answer is simply 1.

Understanding these cases is the key to designing the dynamic programming solution.

Approaches

Brute Force

The most direct solution is to generate every substring of s and every substring of t.

For every pair:

a = substring of s
b = substring of t

construct:

a + b

and test whether it is a palindrome.

There are O(m²) substrings of s and O(n²) substrings of t.

Therefore we examine:

O(m² · n²)

pairs.

Each palindrome check costs up to:

O(m + n)

which makes the total complexity enormous, roughly O(n⁵) when both strings have length 1000.

This is completely infeasible.

Key Insight

Suppose the final palindrome uses characters from both strings.

The left half comes from a suffix of the chosen substring in s, while the right half comes from a prefix of the chosen substring in t.

If we reverse t, then matching characters across the palindrome become a longest common suffix style problem.

Consider:

s = abcde
t = ecdba

Reverse t:

t_rev = abdce

Now a matching mirrored portion corresponds to a common substring ending at positions in s and t_rev.

Let:

dp[i][j]

be the length of the longest matching suffix ending at:

s[i - 1]
t_rev[j - 1]

This is the standard longest common substring recurrence:

if s[i - 1] == t_rev[j - 1]:
    dp[i][j] = dp[i - 1][j - 1] + 1
else:
    dp[i][j] = 0

If a mirrored part contributes k matching pairs, then we already have:

2 * k

palindrome characters.

The remaining center can be a palindrome entirely inside s or entirely inside t.

Therefore we also preprocess:

g1[i] = longest palindromic substring starting at index i in s
g2[i] = longest palindromic substring starting at index i in reversed(t)

Then every matched mirrored segment can be extended with one of these internal palindromes.

This reduces the problem to O(m · n).

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(m² · n² · (m+n))	O(1)	Enumerates every substring pair and checks palindromes
Optimal DP	O(m² + n² + m·n)	O(m·n)	Uses palindrome preprocessing and longest common suffix DP

Algorithm Walkthrough

Step 1: Reverse t

The palindrome condition naturally compares characters from opposite ends.

Reversing t transforms this into a matching substring problem.

t_rev = reverse(t)

Step 2: Compute longest palindrome starting at every index

Create an array:

g[i]

where:

g[i] = length of the longest palindromic substring that starts at i

We compute it by expanding around every possible center.

For each center:

• Expand odd-length palindromes.
• Expand even-length palindromes.

Whenever expansion succeeds from l to r, update:

g[l] = max(g[l], r - l + 1)

Do this once for s and once for t_rev.

Step 3: Initialize the answer

The entire answer may come from only one string.

Therefore:

answer = max(
    longest palindrome in s,
    longest palindrome in t
)

which is:

max(max(g1), max(g2))

Step 4: Build longest common suffix DP

Create:

dp[m+1][n+1]

where:

dp[i][j]

represents the length of the longest matching suffix ending at:

s[i-1]
t_rev[j-1]

Transition:

if s[i-1] == t_rev[j-1]:
    dp[i][j] = dp[i-1][j-1] + 1

Otherwise it remains zero.

Step 5: Use every match as palindrome borders

Suppose:

k = dp[i][j]

Then we have:

k mirrored pairs

which contribute:

2 * k

characters.

The palindrome may continue with an internal palindrome in s.

The next unused position in s is:

i

so we can add:

g1[i]

if it exists.

Candidate:

2*k + g1[i]

Similarly, the center may come from t_rev.

Candidate:

2*k + g2[j]

Update the answer with both values.

Step 6: Return the maximum answer

After processing all DP states, return the largest value found.

Why it works

Every palindrome formed from substrings of both strings consists of three conceptual parts:

matching left border
center palindrome
matching right border

The matching border pairs come from a common substring between s and reverse(t). The DP finds the maximum possible length of every such mirrored border. The preprocessing arrays store the longest palindromic center that can start immediately after the matched border. Since every valid palindrome must have exactly this structure, examining all DP states guarantees that the optimal answer is considered.

Python Solution

from typing import List

class Solution:
    def longestPalindrome(self, s: str, t: str) -> int:
        def expand(string: str, best: List[int], left: int, right: int) -> None:
            n = len(string)

            while left >= 0 and right < n and string[left] == string[right]:
                best[left] = max(best[left], right - left + 1)
                left -= 1
                right += 1

        def calc(string: str) -> List[int]:
            n = len(string)
            best = [0] * n

            for center in range(n):
                expand(string, best, center, center)
                expand(string, best, center, center + 1)

            return best

        m = len(s)
        n = len(t)

        t = t[::-1]

        g1 = calc(s)
        g2 = calc(t)

        answer = max(max(g1), max(g2))

        dp = [[0] * (n + 1) for _ in range(m + 1)]

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if s[i - 1] == t[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1

                    if i < m:
                        answer = max(answer, 2 * dp[i][j] + g1[i])
                    else:
                        answer = max(answer, 2 * dp[i][j])

                    if j < n:
                        answer = max(answer, 2 * dp[i][j] + g2[j])
                    else:
                        answer = max(answer, 2 * dp[i][j])

        return answer

The helper function expand performs the standard center expansion used in longest palindromic substring problems.

For every successful expansion, we update the longest palindrome beginning at the left boundary.

The calc function runs center expansion from every position and produces the array:

g[i]

which sto

Problem Understanding

We are given two stringsating substrings.