Skip to main content
Talentd

Maximize Palindrome Length From Subsequences - Solution & Explanation

HardStringDynamic Programming17 min readAsked at: Goldman Sachs
Practice this problem

Problem Statement

You are given two strings, word1 and word2. You want to construct a string in the following manner:

  • Choose some non-empty subsequence subsequence1 from word1.
  • Choose some non-empty subsequence subsequence2 from word2.
  • Concatenate the subsequences: 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 <= 1000
  • word1 and word2 consist of lowercase English letters.

Approach Overview

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 1: Dynamic Programming on Concatenated String

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.

Code

PythonJavaC++JavaScriptC#C

Python

Java

C++

JavaScript

C#

C

Complexity

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.

Try this approach in the editor →

Approach 2: Two-Part Dynamic Programming

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.

Code

Python

Python

Complexity

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).

Try this approach in the editor →

Approach 3: Dynamic Programming

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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming on Concatenated String

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.

Two-Part Dynamic Programming

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).

Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dynamic Programming on Concatenated StringO(n^2)O(n^2)General solution. Cleanest way to enforce the requirement that the palindrome uses characters from both strings.
Two-Part Dynamic ProgrammingO(n^2)O(n^2)Useful when reasoning about cross-string pairing explicitly using LCS-style DP.

Video Solution

LeetCode 1771 Maximize Palindrome Length From Subsequences | Weekly Contest 229 | C++ • Cherry Coding [IIT-G] • 1,337 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Maximize Palindrome Length From Subsequences easy or hard?
Maximize Palindrome Length From Subsequences is labeled Hard on LeetCode with an acceptance rate around 38%. The difficulty comes from recognizing it as a longest palindromic subsequence variant and enforcing the constraint that the final palindrome must use characters from both strings.
Maximize Palindrome Length From Subsequences Python/Java solution
Most implementations build a DP table over the concatenated string and fill it using bottom-up interval dynamic programming. The same logic works in Python, Java, C++, JavaScript, and C#. Each language version iterates over substring lengths and updates dp[i][j] using the LPS recurrence.
How to solve Maximize Palindrome Length From Subsequences in O(n^2)?
Concatenate the strings into a single string and compute the longest palindromic subsequence using interval dynamic programming. While evaluating pairs of indices (i, j), update the answer only when i belongs to word1 and j belongs to word2. This ensures the palindrome is built from subsequences of both strings. The DP transitions follow the classic LPS recurrence.
What is the best approach for Maximize Palindrome Length From Subsequences?
The most reliable approach uses dynamic programming on the concatenated string word1 + word2. Build a DP table for the longest palindromic subsequence and only count pairs where the left index comes from word1 and the right index comes from word2. This guarantees the palindrome includes characters from both strings. The solution runs in O(n^2) time and O(n^2) space.
Is Maximize Palindrome Length From Subsequences asked at Google/Amazon/Meta?
Palindrome subsequence and interval dynamic programming problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of longest palindromic subsequence and cross-string DP are common because they test understanding of DP state transitions and string manipulation.
What data structure is used in Maximize Palindrome Length From Subsequences?
The core data structure is a 2D dynamic programming table where dp[i][j] represents the longest palindromic subsequence inside substring s[i..j]. The algorithm also relies on string indexing and interval traversal from smaller substrings to larger ones.
What is the time complexity of Maximize Palindrome Length From Subsequences?
The optimal dynamic programming solution runs in O(n^2) time where n is the combined length of word1 and word2. A 2D DP table stores the longest palindromic subsequence for every substring. Space complexity is also O(n^2) due to the DP matrix.

Ready to solve this problem?

Practice Maximize Palindrome Length From Subsequences with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Palindromic Subsequence