Longest Palindrome After Substring Concatenation I - Video Solutions

Problem Overview: You are given two strings and can choose any substring from each, concatenate them, and form a new string. The goal is to compute the maximum possible length of a palindrome that can be formed after this concatenation.

The challenge is that the palindrome may span across the boundary where the two substrings meet. A naive search over all substring pairs quickly becomes expensive, so the key is detecting palindromes efficiently while considering combinations from both strings.

Approach 1: Brute Force Substring Enumeration (O(n⁴) time, O(1) space)

Generate every substring of the first string and every substring of the second string. Concatenate each pair and check whether the result is a palindrome using a two‑pointer comparison from both ends. This requires iterating through O(n²) substrings per string, leading to O(n⁴) combinations overall. Palindrome validation itself costs O(n), making the total complexity even worse in practice. This approach is useful only for understanding the problem constraints or validating small inputs.

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

The optimized solution observes that any palindrome can be described by a center (single character or gap between characters). Instead of building every concatenated string, enumerate possible palindrome centers and expand outward using the classic center‑expansion technique from two pointers. While expanding, track how characters from the first and second substrings mirror each other.

Dynamic programming helps precompute whether substrings inside each string are palindromes. A DP table dp[i][j] stores whether the substring from index i to j forms a palindrome. With this information, once the cross‑boundary characters match, you can instantly verify whether the remaining portion inside either string is already a palindrome. This avoids repeatedly recomputing palindrome checks.

The algorithm effectively combines enumeration of palindrome centers with substring palindrome checks from dynamic programming. Each center expansion takes linear time and there are O(n²) relevant combinations across the two strings, producing an overall O(n²) runtime.

Recommended for interviews: Interviewers expect the center‑expansion + DP idea. Starting with brute force shows you understand the search space, but recognizing that palindromes can be expanded from centers and accelerated with DP demonstrates strong string algorithm intuition and optimization skills.