#3503

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Longest Palindrome After Substring Concatenation I

Compute the maximum palindrome length by concatenating substrings from two strings using state transition dynamic programming efficiently.

two pointers string dynamic programming enumeration

Problem Statement

You are given two strings s and t consisting of lowercase English letters. You may select any substring from s and any substring from t and concatenate them in order to create a new string.

Return the length of the longest palindrome that can be formed from such a concatenation. A palindrome reads the same forwards and backwards, and the chosen substrings can be empty. Optimize using state transition dynamic programming rather than brute force.

Examples

Example 1

Input: s = "a", t = "a"

Output: 2

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

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

Selecting " aaaa " from t is the longest palindrome, so the answer is 4.

Constraints

1 <= s.length, t.length <= 30
s and t consist of lowercase English letters.

Solution Approach

Dynamic Programming Table

Construct a DP table where dp[i][j] represents the longest palindrome length using s prefix of length i and t suffix of length j. Update states by comparing characters at s[i-1] and t[j-1] and merging results.

Two Pointer Expansion

For each concatenation candidate, use two pointers to expand from center substrings and track the maximum palindrome length efficiently. This complements DP by validating actual palindromes across concatenation points.

Enumerate Substrings with Memoization

Iterate through all possible substrings from s and t, but store intermediate results in a memoization structure to avoid redundant computation. This balances enumeration with DP to respect the problem constraints.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n^2 * m^2) in the worst case where n and m are lengths of s and t due to substring enumeration, but DP and memoization reduce repeated work. Space complexity is O(n * m) for storing DP states.

What Interviewers Usually Probe

Candidate considers all substring concatenations and identifies overlapping subproblems.
Candidate correctly implements state transition DP rather than naive brute force.
Candidate can explain why two pointers validate palindrome expansion efficiently.

Common Pitfalls or Variants

Common pitfalls

Attempting pure brute force without DP leads to excessive computation.
Ignoring empty substring cases causes off-by-one errors in palindrome length.
Failing to track palindrome expansion across s and t boundaries results in undercounted lengths.

Follow-up variants

Allowing multiple concatenations of substrings instead of just one.
Restricting palindrome formation to contiguous concatenation only.
Finding the actual palindrome string, not just its length.

FAQ

What is the main pattern used in Longest Palindrome After Substring Concatenation I?

The problem relies on state transition dynamic programming to handle substring concatenations and track palindrome lengths.

Can empty substrings be used when forming the palindrome?

Yes, empty substrings from s or t are allowed and may contribute to maximizing the palindrome length.

How does the two pointer technique help?

Two pointers efficiently expand around concatenation centers to verify the maximum palindrome without recomputation.

What are common pitfalls when solving this problem?

Ignoring empty substrings, using brute force without DP, and failing to track overlapping substrings across s and t.

Is memoization necessary in this problem?

Memoization reduces repeated computations when enumerating all substring concatenations, making DP practical for the constraints.

terminal

Solution

Solution 1: Enumerate Palindrome Centers + Dynamic Programming

According to the problem description, the concatenated palindrome string can be composed entirely of string $s$, entirely of string $t$, or a combination of both strings $s$ and $t$. Additionally, there may be extra palindromic substrings in either string $s$ or $t$.

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

class Solution:
    def longestPalindrome(self, s: str, t: str) -> int:
        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

        def calc(s: str) -> List[int]:
            n = len(s)
            g = [0] * n
            for i in range(n):
                expand(s, g, i, i)
                expand(s, g, i, i + 1)
            return g

        m, n = len(s), len(t)
        t = t[::-1]
        g1, g2 = calc(s), calc(t)
        ans = max(*g1, *g2)
        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
                    ans = max(ans, f[i][j] * 2 + (0 if i >= m else g1[i]))
                    ans = max(ans, f[i][j] * 2 + (0 if j >= n else g2[j]))
        return ans

Continue Practicing

#3504 longest palindrome after substring concatenation ii #3403 find the lexicographically largest string from the box i #3389 minimum operations to make character frequencies equal