Watch 8 video solutions for Maximize Palindrome Length From Subsequences, a hard level problem involving String, Dynamic Programming. This walkthrough by Cherry Coding [IIT-G] has 1,304 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |