You are given two strings, word1 and word2. You want to construct a string in the following manner:
subsequence1 from word1.subsequence2 from word2.subsequence1 + subsequence2, to make the string.Return the length of the longest palindrome that can be constructed in the described manner. If no palindromes can be constructed, return 0.
A subsequence of a string s is a string that can be made by deleting some (possibly none) characters from s without changing the order of the remaining characters.
A palindrome is a string that reads the same forward as well as backward.
Example 1:
Input: word1 = "cacb", word2 = "cbba" Output: 5 Explanation: Choose "ab" from word1 and "cba" from word2 to make "abcba", which is a palindrome.
Example 2:
Input: word1 = "ab", word2 = "ab" Output: 3 Explanation: Choose "ab" from word1 and "a" from word2 to make "aba", which is a palindrome.
Example 3:
Input: word1 = "aa", word2 = "bb" Output: 0 Explanation: You cannot construct a palindrome from the described method, so return 0.
Constraints:
1 <= word1.length, word2.length <= 1000word1 and word2 consist of lowercase English letters.Problem Overview: You are given two strings word1 and word2. Pick a subsequence from each string, concatenate them, and form the longest possible palindrome. The result must use characters from both strings.
Approach 1: Dynamic Programming on Concatenated String (O(n^2) time, O(n^2) space)
Concatenate the strings into s = word1 + word2. The problem becomes a variation of the Longest Palindromic Subsequence (LPS). Build a 2D DP table where dp[i][j] stores the length of the longest palindromic subsequence in substring s[i..j]. Fill the table using the standard recurrence: if s[i] == s[j], then dp[i][j] = dp[i+1][j-1] + 2; otherwise take max(dp[i+1][j], dp[i][j-1]). The key constraint is ensuring the palindrome uses characters from both strings. While evaluating pairs (i, j), update the answer only when i lies in word1 and j lies in word2. This guarantees the palindrome includes characters from both halves. This approach leverages classic dynamic programming on a string interval and works efficiently for lengths up to ~2000.
Approach 2: Two-Part Dynamic Programming (O(n^2) time, O(n^2) space)
Another perspective separates the cross-string pairing from the inner palindrome expansion. First compute the longest common subsequence (LCS) between word1 and reverse(word2). Each matched pair forms the outer symmetric characters of the palindrome. After fixing these boundary pairs, the remaining middle portion becomes a standard longest palindromic subsequence problem inside the combined range. You maintain DP states that track subsequences built from word1 and mirrored characters from word2. This decomposition makes the “use both strings” constraint explicit, though the state transitions are slightly more complex than the concatenation method.
Recommended for interviews: The concatenated-string DP is what most interviewers expect. It shows you recognize the problem as a constrained Longest Palindromic Subsequence variant and can adapt interval DP to enforce the cross-string condition. Mentioning brute LPS first demonstrates understanding, then adding the boundary check between word1 and word2 shows the optimization needed for the final answer.
Concatenate the two strings and compute the longest palindromic subsequence (LPS) of the concatenated string using dynamic programming. Then, check if the subsequence uses characters from both strings.
This solution calculates the longest palindromic subsequence of the concatenated strings word1+word2 using dynamic programming. After that, it checks palindromes that include characters from both word1 and word2.
Time Complexity: O((n+m)^2), where n and m are the lengths of word1 and word2. Space Complexity: O((n+m)^2) for the DP table.
Utilize two separate DP tables to find the longest palindromic subsequence within each word and then seek potential matches at the crossover of the two strings.
This approach calculates the longest palindromic subsequence for both words individually. Then it checks for the longest palindrome that can be constructed by joining subsequences from word1 and word2.
Python
Time Complexity: O(n^2 + m^2), where n and m are the lengths of word1 and word2 respectively. Space Complexity: O(n^2 + m^2).
First, we concatenate strings word1 and word2 to get string s. Then we can transform the problem into finding the length of the longest palindromic subsequence in string s. However, when calculating the final answer, we need to ensure that at least one character in the palindrome string comes from word1 and another character comes from word2.
We define f[i][j] as the length of the longest palindromic subsequence in the substring of string s with index range [i, j].
If s[i] = s[j], then s[i] and s[j] must be in the longest palindromic subsequence, at this time f[i][j] = f[i + 1][j - 1] + 2. At this point, we also need to judge whether s[i] and s[j] come from word1 and word2. If so, we update the maximum value of the answer to ans=max(ans, f[i][j]).
If s[i] neq s[j], then s[i] and s[j] will definitely not appear in the longest palindromic subsequence at the same time, at this time f[i][j] = max(f[i + 1][j], f[i][j - 1]).
Finally, we return the answer.
The time complexity is O(n^2), and the space complexity is O(n^2). Here, n is the length of string s.
| Approach | Complexity |
|---|---|
| Dynamic Programming on Concatenated String | Time Complexity: O((n+m)^2), where n and m are the lengths of |
| Two-Part Dynamic Programming | Time Complexity: O(n^2 + m^2), where n and m are the lengths of |
| Dynamic Programming | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming on Concatenated String | O(n^2) | O(n^2) | General solution. Cleanest way to enforce the requirement that the palindrome uses characters from both strings. |
| Two-Part Dynamic Programming | O(n^2) | O(n^2) | Useful when reasoning about cross-string pairing explicitly using LCS-style DP. |
LeetCode 1771 Maximize Palindrome Length From Subsequences | Weekly Contest 229 | C++ • Cherry Coding [IIT-G] • 1,304 views views
Watch 7 more video solutions →Practice Maximize Palindrome Length From Subsequences with our built-in code editor and test cases.
Practice on FleetCode