Problem Description

You are given two strings s and t.

You need to find the longest possible palindrome that can be created by:

1. Selecting a substring from s (which can be empty)
2. Selecting a substring from t (which can be empty)
3. Concatenating them in that order (substring from s followed by substring from t)

The task is to return the length of the longest palindrome that can be formed this way.

For example, if you have strings s and t, you could:

• Use only a palindromic substring from s (leaving t's contribution empty)
• Use only a palindromic substring from t (leaving s's contribution empty)
• Use a substring from s concatenated with a substring from t that together form a palindrome

The key insight is that when concatenating substrings from both strings to form a palindrome, the ending portion of the substring from s must match (in reverse) with the beginning portion of the substring from t. This creates a palindromic structure where the first part mirrors the second part.

The solution approach involves:

• Preprocessing both strings to find all palindromic substrings starting at each position
• Using dynamic programming to find matching sequences between s and the reverse of t
• Considering cases where additional palindromic content exists in either string beyond the matching portion
• Tracking the maximum palindrome length across all possible combinations

Intuition

To understand how to build the longest palindrome from two strings, let's think about what palindromes look like when formed from concatenated substrings.

A palindrome reads the same forwards and backwards. When we concatenate a substring from s with a substring from t, we get three possible scenarios:

1. The palindrome comes entirely from one string: We simply need to find the longest palindromic substring in either s or t.

2. The palindrome spans both strings: This is the interesting case. For the concatenated result to be a palindrome, the end of the substring from s must mirror the beginning of the substring from t.

Think of it this way: if we have "abc" from s and "cba" from t, concatenating gives us "abccba" - a palindrome! The key observation is that the substring from t needs to be the reverse of the substring from s for the concatenation to form a palindrome.

This leads us to reverse string t first. Now, finding matching parts between s and reversed t becomes a problem of finding common substrings, which we can solve with dynamic programming. When s[i] == reversed_t[j], we can extend our palindrome.

But there's another layer: what if after matching some characters between s and reversed t, there's still a palindromic tail in s or a palindromic head in reversed t? For example, if we match "ab" from s with "ba" from reversed t to get "abba", but s actually has "abcbc" where "cbc" is also a palindrome, we can include it to get "abcbcba"!

This is why we precompute g1[i] and g2[j] - they tell us the longest palindrome starting at position i in s and position j in reversed t respectively. After finding matching portions with DP, we check if we can extend the palindrome further using these precomputed values.

The formula f[i][j] * 2 + g1[i] represents: the matched portion doubled (since it appears in both halves of the palindrome) plus any additional palindromic content that can be added from the middle outward.

Learn more about Two Pointers and Dynamic Programming patterns.

Solution Approach

The implementation consists of three main components: preprocessing palindromes, reversing string t, and dynamic programming to find the longest palindrome.

Step 1: Preprocessing Palindromic Substrings

The calc function finds the longest palindromic substring starting at each position. It uses the expand helper function to check palindromes by expanding from centers:

• For each position i, we try two types of centers:
  • Odd-length palindromes: expand from (i, i)
  • Even-length palindromes: expand from (i, i+1)
• The expand function updates g[l] with the maximum palindrome length starting at position l

def expand(s: str, g: List[int], l: int, r: int):
    while l >= 0 and r < len(s) and s[l] == s[r]:
        g[l] = max(g[l], r - l + 1)
        l, r = l - 1, r + 1

Step 2: Reverse String t and Initialize

We reverse string t because we need to find matching sequences between the end of substring from s and the beginning of substring from t:

t = t[::-1]
g1, g2 = calc(s), calc(t)
ans = max(*g1, *g2)  # Initialize with longest palindrome from single string

Step 3: Dynamic Programming for Matching Sequences

We create a 2D DP table f[i][j] where f[i][j] represents the length of matching sequence ending at position i-1 in s and position j-1 in reversed t:

f = [[0] * (n + 1) for _ in range(m + 1)]
for i, a in enumerate(s, 1):
    for j, b in enumerate(t, 1):
        if a == b:
            f[i][j] = f[i - 1][j - 1] + 1

When characters match (a == b), we extend the matching sequence by 1.

Step 4: Calculate Maximum Palindrome Length

For each matching position, we consider two cases for extending the palindrome:

1. Extend with remaining palindrome from s:

   ans = max(ans, f[i][j] * 2 + (0 if i >= m else g1[i]))

   • f[i][j] * 2: The matched portion appears twice (once from s, once from reversed t)
   • g1[i]: Additional palindrome starting from position i in s (if not at end)

2. Extend with remaining palindrome from reversed t:

   ans = max(ans, f[i][j] * 2 + (0 if j >= n else g2[j]))

   • Similar logic but using g2[j] for the palindrome in reversed t

The final answer is the maximum palindrome length found across all possibilities.

Time Complexity: O(m*n) where m and n are lengths of strings s and t Space Complexity: O(m*n) for the DP table

Example Walkthrough

Let's walk through the solution with s = "abcd" and t = "dcba".

Step 1: Preprocess palindromic substrings

For s = "abcd":

• Position 0 ('a'): longest palindrome starting here = 1 ("a")
• Position 1 ('b'): longest palindrome starting here = 1 ("b")
• Position 2 ('c'): longest palindrome starting here = 1 ("c")
• Position 3 ('d'): longest palindrome starting here = 1 ("d") So g1 = [1, 1, 1, 1]

For t = "dcba":

• Position 0 ('d'): longest palindrome starting here = 1 ("d")
• Position 1 ('c'): longest palindrome starting here = 1 ("c")
• Position 2 ('b'): longest palindrome starting here = 1 ("b")
• Position 3 ('a'): longest palindrome starting here = 1 ("a") So g2_original = [1, 1, 1, 1]

Step 2: Reverse string t

After reversing: t = "abcd" (reversed from "dcba") Now g2 = [1, 1, 1, 1] (positions correspond to reversed string)

Initialize ans = 1 (maximum from single character palindromes)

Step 3: Build DP table for matching sequences

We build f[i][j] where f[i][j] represents length of matching sequence ending at s[i-1] and t[j-1]:

    ""  a  b  c  d  (reversed t)
""  0   0  0  0  0
a   0   1  0  0  0
b   0   0  2  0  0  
c   0   0  0  3  0
d   0   0  0  0  4
(s)

Key matches:

• f[1][1] = 1: "a" matches "a"
• f[2][2] = 2: "ab" matches "ab"
• f[3][3] = 3: "abc" matches "abc"
• f[4][4] = 4: "abcd" matches "abcd"

Step 4: Calculate maximum palindrome

For each non-zero f[i][j], we check:

At f[1][1] = 1 (matched "a" from s and "a" from reversed t):

• Case 1: 1 * 2 + g1[1] = 2 + 1 = 3 (palindrome: "aba")
• Case 2: 1 * 2 + g2[1] = 2 + 1 = 3 (palindrome: "aba")
• Update ans = 3

At f[2][2] = 2 (matched "ab" from s and "ab" from reversed t):

• Case 1: 2 * 2 + g1[2] = 4 + 1 = 5 (palindrome: "abcba")
• Case 2: 2 * 2 + g2[2] = 4 + 1 = 5 (palindrome: "abcba")
• Update ans = 5

At f[3][3] = 3 (matched "abc" from s and "abc" from reversed t):

• Case 1: 3 * 2 + g1[3] = 6 + 1 = 7 (palindrome: "abcdcba")
• Case 2: 3 * 2 + g2[3] = 6 + 1 = 7 (palindrome: "abcdcba")
• Update ans = 7

At f[4][4] = 4 (matched "abcd" from s and "abcd" from reversed t):

• Case 1: 4 * 2 + 0 = 8 (i >= m, so no more characters in s)
• Case 2: 4 * 2 + 0 = 8 (j >= n, so no more characters in reversed t)
• Update ans = 8

Final Result: 8

The longest palindrome is "abcddcba" formed by taking "abcd" from s and "dcba" from t.

Solution Implementation

Time and Space Complexity

The time complexity of this code is O(m² + n² + m × n), where m is the length of string s and n is the length of string t.

Breaking down the time complexity:

• The calc function is called twice - once for string s and once for reversed string t
• For calc(s): The function iterates through each position in the string (O(m) iterations), and for each position, calls expand twice. The expand function can potentially check up to O(m) characters in the worst case (expanding from center to edges). This gives O(m²) for processing string s
• For calc(t): Similarly, this takes O(n²) for processing reversed string t
• The nested loops for dynamic programming iterate m × n times, with O(1) operations in each iteration, contributing O(m × n)
• Total: O(m² + n² + m × n)

However, the reference answer states O(m × (m + n)). This appears to be a simplification or different interpretation. If we consider that typically m and n are of similar magnitude, or if m ≥ n, then O(m² + n² + m × n) could be bounded by O(m × (m + n)).

The space complexity is O(m × n), where:

• The 2D array f uses O((m + 1) × (n + 1)) = O(m × n) space
• Arrays g1 and g2 use O(m) and O(n) space respectively
• Total: O(m × n + m + n) = O(m × n) (since m × n dominates for non-trivial inputs)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Palindrome Extension Logic

Pitfall: A common mistake is incorrectly calculating the total palindrome length when combining matched sequences with remaining palindromes. Developers often forget that the matched portion contributes twice to the final length (once from s and once from reversed t).

Incorrect Implementation:

# Wrong: Only counting matched portion once
ans = max(ans, f[i][j] + g1[i])  # Missing multiplication by 2

Correct Implementation:

# Correct: Matched portion appears twice in the final palindrome
ans = max(ans, f[i][j] * 2 + (0 if i >= m else g1[i]))

2. Off-by-One Errors in DP Indexing

Pitfall: The DP table uses 1-indexed positions while the palindrome arrays use 0-indexed positions. This mismatch frequently causes index errors when accessing the palindrome length arrays.

Incorrect Implementation:

for i in range(1, m + 1):
    for j in range(1, n + 1):
        if s[i-1] == t_reversed[j-1]:
            f[i][j] = f[i-1][j-1] + 1
            # Wrong: Using 1-indexed i directly with 0-indexed g1
            ans = max(ans, f[i][j] * 2 + g1[i])  # IndexError when i == m

Correct Implementation:

for i, char_s in enumerate(s, 1):  # i is 1-indexed
    for j, char_t in enumerate(t_reversed, 1):  # j is 1-indexed
        if char_s == char_t:
            dp[i][j] = dp[i-1][j-1] + 1
            # Correct: Check bounds and use proper index
            if i < m:  # Ensure i is valid index for g1 (0-indexed)
                ans = max(ans, dp[i][j] * 2 + g1[i])

3. Forgetting to Consider Single-String Palindromes

Pitfall: Only focusing on concatenated palindromes and forgetting that the longest palindrome might come from just one string alone.

Incorrect Implementation:

ans = 0  # Wrong: Starting with 0 ignores single-string palindromes
# ... DP logic ...
return ans

Correct Implementation:

# Initialize with the longest palindrome from either string alone
ans = max(*g1, *g2)
# ... DP logic ...
return ans

4. Not Handling Edge Cases Properly

Pitfall: Failing to handle edge cases when one or both strings are empty, or when the matching sequence extends to the end of either string.

Solution: Always check boundaries before accessing array elements:

# Check if there are remaining characters before accessing palindrome arrays
if i < m:
    ans = max(ans, dp[i][j] * 2 + palindrome_lengths_s[i])
else:
    ans = max(ans, dp[i][j] * 2)  # No remaining characters to add

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

5. Misunderstanding the Problem Requirements

Pitfall: Thinking that the entire strings must be used, or that the substrings must be contiguous in a specific way.

Key Understanding:

• Substrings from s and t can be empty
• The concatenation order matters (substring from s first, then from t)
• The goal is to form a palindrome, which requires the end of the s substring to match (in reverse) with the beginning of the t substring

Implementation Tip: Reversing t at the beginning simplifies the matching logic, as you're now looking for common prefixes between s and reversed t.