Skip to main content
Talentd

Longest Palindrome After Substring Concatenation II - Solution & Explanation

HardTwo PointersStringDynamic Programming11 min readAsked at: Google
Practice this problem

Problem Statement

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.

Approach Overview

Problem Overview: You are given two strings and can pick a substring from each, concatenate them, and form a new string. The task is to compute the maximum possible length of a palindrome that can be created from such a concatenation.

Approach 1: Brute Force Substring Enumeration (O(n^2 * m^2 * L) time, O(1) space)

Enumerate every substring from the first string and every substring from the second string. Concatenate them and check whether the resulting string is a palindrome using a two-pointer scan from both ends. If the string length is L, the palindrome check costs O(L). Since there are O(n^2) substrings in the first string and O(m^2) in the second, the total work grows quickly. This approach is mainly useful to understand the search space but becomes infeasible for larger inputs.

Approach 2: Enumerate Palindrome Centers + Dynamic Programming (O(n*m + n^2 + m^2) time, O(n^2 + m^2) space)

The key observation is that a valid palindrome can span the boundary between the chosen substrings. Treat that boundary as the center of the palindrome and expand outward using the two pointers technique. While expanding, characters must match between the suffix of the first substring and the prefix of the second substring.

Precompute palindrome information inside each string using dynamic programming. A DP table dp[i][j] indicates whether s[i..j] is a palindrome. This lets you extend a cross-string match with additional characters from either side if they already form a palindrome internally. During enumeration, match characters across both strings and track the longest symmetric expansion.

This converts the problem from checking all concatenations to expanding around possible centers and reusing precomputed palindrome segments. Most of the work becomes linear scans with constant-time DP lookups. The combination of center expansion and DP pruning drastically reduces repeated palindrome checks while still covering every valid construction.

Recommended for interviews: The palindrome-center enumeration with dynamic programming is the expected solution. Interviewers want to see recognition that concatenation palindromes behave like center expansions across two strings. Mentioning the brute force approach first shows understanding of the search space, while the optimized solution demonstrates skill with string processing, two-pointer expansion, and DP preprocessing.

Solution

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.

Therefore, we first reverse string t and preprocess arrays g1 and g2, where g1[i] represents the length of the longest palindromic substring starting at index i in string s, and g2[i] represents the length of the longest palindromic substring starting at index i in string t.

We can initialize the answer ans as the maximum value in g1 and g2.

Next, we define f[i][j] as the length of the palindromic substring ending at the i-th character of string s and the j-th character of string t.

For f[i][j], if s[i - 1] equals t[j - 1], then f[i][j] = f[i - 1][j - 1] + 1. We then update the answer:

$ ans = max(ans, f[i][j] times 2 + (0 if i geq m else g1[i])) \ ans = max(ans, f[i][j] times 2 + (0 if j geq n else g2[j]))

Finally, we return the answer ans.

The time complexity is O(m times (m + n)), and the space complexity is O(m times n), where m and n are the lengths of strings s and t$, respectively.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Substring EnumerationO(n^2 * m^2 * L)O(1)Useful for understanding the search space or validating small inputs
Enumerate Palindrome Centers + Dynamic ProgrammingO(n*m + n^2 + m^2)O(n^2 + m^2)General case and interview solution when strings are moderately large

Video Solution

Longest Palindrome After Substring Concatenation II (Leetcode Weekly 443) • Soumya Bhattacharjee • 1,230 views views

Watch 3 more video solutions →

Frequently Asked Questions

Is Longest Palindrome After Substring Concatenation II easy or hard?
Longest Palindrome After Substring Concatenation II is classified as a Hard problem. The difficulty comes from recognizing that the palindrome can span two different substrings and that naive concatenation checks are too slow. Efficient solutions combine center expansion, dynamic programming, and careful boundary handling.
Longest Palindrome After Substring Concatenation II Python/Java solution
Implement the optimized approach by first building DP tables for palindromic substrings in each string. Then iterate over possible boundary centers and expand with two pointers while characters match. The same logic translates cleanly across Python, Java, C++, Go, and TypeScript since it relies on array indexing and nested loops.
How to solve Longest Palindrome After Substring Concatenation II in O(n*m)?
Use palindrome center expansion across the concatenation boundary. Precompute palindromic substrings inside each string with dynamic programming so you can extend matches efficiently. During expansion, match characters from the first string moving left and the second string moving right. With DP lookups for internal palindromes, the cross comparisons dominate the runtime at about O(n*m).
What is the best approach for Longest Palindrome After Substring Concatenation II?
The most effective approach enumerates palindrome centers across the boundary of the two chosen substrings and uses dynamic programming to precompute palindromic segments within each string. Two pointers expand outward while characters match between the suffix of the first string and the prefix of the second. DP tables allow constant-time checks for internal palindrome extensions. This reduces repeated checks and runs in roughly O(n*m + n^2 + m^2) time.
Is Longest Palindrome After Substring Concatenation II asked at Google/Amazon/Meta?
Palindrome construction and substring combination problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variants that combine dynamic programming with two-pointer expansion are especially common because they test string manipulation, optimization, and reasoning about symmetry.
What data structure is used in Longest Palindrome After Substring Concatenation II?
The solution mainly relies on dynamic programming tables to store palindrome states for substrings. Two pointers are used to expand around potential palindrome centers across the concatenation boundary. Basic string indexing and DP matrices are the primary data structures involved.
What is the time complexity of Longest Palindrome After Substring Concatenation II?
The optimized solution runs in O(n*m + n^2 + m^2) time and O(n^2 + m^2) space. The n^2 and m^2 components come from dynamic programming tables that store whether substrings inside each string are palindromes. The cross-string expansion phase checks matches between both strings using two pointers.

Ready to solve this problem?

Practice Longest Palindrome After Substring Concatenation II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Edit Distance