Watch 4 video solutions for Longest Palindrome After Substring Concatenation II, a hard level problem involving Two Pointers, String, Dynamic Programming. This walkthrough by Soumya Bhattacharjee has 1,209 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 1000s and t consist of lowercase English letters.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.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Substring Enumeration | O(n^2 * m^2 * L) | O(1) | Useful for understanding the search space or validating small inputs |
| Enumerate Palindrome Centers + Dynamic Programming | O(n*m + n^2 + m^2) | O(n^2 + m^2) | General case and interview solution when strings are moderately large |