#3504

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Longest Palindrome After Substring Concatenation II

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

two pointers string dynamic programming

Problem Statement

Given two strings s and t, you can form a new string by selecting any substring from s and any substring from t, then concatenating them in order. The task is to find the maximum length palindrome that can be created using this method.

Return an integer representing the length of the longest palindrome that can be obtained from these concatenated substrings. The strings consist only of lowercase English letters, and substrings can be empty, so edge cases with single characters or empty selections should be considered.

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 <= 1000
s and t consist of lowercase English letters.

Solution Approach

Define DP State

Let dp[i][j] represent the length of the longest palindrome starting with s[i] and ending with t[j]. This captures all valid concatenation scenarios and ensures overlapping substrings are correctly evaluated.

Transition Rules

Use a two-pointer approach on both s and t while updating dp[i][j] by expanding palindromes or skipping characters. Match characters from s and t to grow potential palindromes while recording the maximum length.

Edge Cases and Optimization

Handle single-character substrings and empty selections explicitly. Optimize by caching previously computed dp values and avoid recomputation for overlapping indices to maintain efficiency within the given constraints.

Complexity Analysis

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

Time complexity is roughly O(n m) due to evaluating all combinations of start indices from s and end indices from t. Space complexity is O(n m) for storing dp values, where n and m are the lengths of s and t.

What Interviewers Usually Probe

Expect candidates to define dp[i][j] for substring start and end positions.
Watch for correct handling of empty substrings and single-character edge cases.
Look for efficient memoization or bottom-up DP rather than brute-force substring concatenation.

Common Pitfalls or Variants

Common pitfalls

Overlooking the possibility of empty substrings leading to miscalculated palindrome length.
Failing to correctly match characters at the edges of s and t when expanding palindromes.
Using brute-force concatenation without dynamic programming causes TLE for larger inputs.

Follow-up variants

Compute longest palindrome using a single string repeated twice instead of two separate strings.
Find the longest palindrome after concatenating up to k substrings from s and t alternately.
Determine the number of distinct palindromes that can be formed from concatenated substrings of s and t.

FAQ

What is the main idea behind Longest Palindrome After Substring Concatenation II?

The key is using state transition dynamic programming to track possible start and end indices in s and t, combining substrings efficiently.

Can substrings be empty when forming the palindrome?

Yes, both substrings from s and t can be empty, which should be handled explicitly in the DP setup.

How do two pointers help in this problem?

Two pointers allow simultaneous traversal of s and t to expand candidate palindromes and update dp values efficiently.

What is the worst-case time complexity?

The worst-case time complexity is O(n*m), where n and m are the lengths of s and t, due to evaluating all start-end pairs.

Are single-character palindromes considered valid results?

Yes, when no longer palindrome exists, a single character from s or t counts as a valid palindrome of length 1.

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

#3503 longest palindrome after substring concatenation i #3316 find maximum removals from source string #3302 find the lexicographically smallest valid sequence