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.

Description Hints 2 Solution Video 13:30

1771. Maximize Palindrome Length From Subsequences

Hard39.0% acceptance1 company

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.

Asked at 1 company

Goldman Sachs

Topics

Dynamic Programming String

Hints open one at a time

Hint 1

Let's ignore the non-empty subsequence constraint. We can concatenate the two strings and find the largest palindromic subsequence with dynamic programming.

Hint 2

Iterate through every pair of characters word1[i] and word2[j], and see if some palindrome begins with word1[i] and ends with word2[j]. This ensures that the subsequences are non-empty.

13:30

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution