LeetCode 1771 - Maximize Palindrome Length From Subsequences

The problem gives us two strings, word1 and word2. We must choose a non-empty subsequence from each string, concatenate them together, and form a palindrome. Our goal is to maximize the length of that palindrome. A subsequence does not require characters to be contiguous.

leetcodehardstringdynamic-programming

LeetCode Problem 1771

Difficulty: 🔴 Hard
Topics: String, Dynamic Programming

Solution

Problem Understanding

The problem gives us two strings, word1 and word2. We must choose a non-empty subsequence from each string, concatenate them together, and form a palindrome. Our goal is to maximize the length of that palindrome.

A subsequence does not require characters to be contiguous. We are allowed to skip characters as long as the remaining characters preserve their original order. This flexibility is important because it means we are effectively searching through many possible combinations.

The key restriction is that the final palindrome must use at least one character from word1 and at least one character from word2. We are not allowed to take the entire palindrome from only one string.

The input sizes are important:

  • 1 <= word1.length, word2.length <= 1000

This means the total combined length can reach 2000. A brute-force search over all subsequences is completely infeasible because the number of subsequences grows exponentially.

The expected output is a single integer representing the maximum possible palindrome length. If no palindrome can be formed using characters from both strings, we return 0.

Several edge cases are important:

  • The two strings may share no common characters at all, making it impossible to form a valid palindrome.
  • The optimal palindrome may not use all characters.
  • The palindrome may have either even or odd length.
  • A naive longest palindromic subsequence solution on the concatenated string is not enough, because we must guarantee usage of both original strings.

The core challenge is therefore not just finding a palindrome, but finding one whose left and right portions cross the boundary between the two strings.

Approaches

Brute Force Approach

A brute-force solution would generate every non-empty subsequence of word1 and every non-empty subsequence of word2. For each pair, we concatenate them and check whether the resulting string is a palindrome.

Suppose word1 has length n and word2 has length m.

  • word1 has 2^n - 1 non-empty subsequences.
  • word2 has 2^m - 1 non-empty subsequences.

We would therefore examine roughly:

$$(2^n - 1)(2^m - 1)$$

possible concatenations.

Even for strings of length 30, this becomes astronomically large. With lengths up to 1000, this approach is impossible.

The brute-force method is conceptually correct because it exhaustively checks every valid construction, but it cannot satisfy the constraints.

Optimal Dynamic Programming Insight

The key observation is that the problem can be transformed into a longest palindromic subsequence problem on the concatenated string:

s = word1 + word2

However, we cannot simply compute the longest palindromic subsequence of s, because that palindrome might lie entirely inside one string.

The important insight is this:

  • Any valid palindrome must contain at least one matching pair where:

  • the left character comes from word1

  • the right character comes from word2

Once we identify such a matching pair, the interior portion can be any palindromic subsequence between them.

This naturally suggests interval dynamic programming.

Define:

dp[i][j]

as the length of the longest palindromic subsequence inside s[i:j+1].

The recurrence is the standard longest palindromic subsequence recurrence:

  • If s[i] == s[j]:
dp[i][j] = dp[i+1][j-1] + 2
  • Otherwise:
dp[i][j] = max(dp[i+1][j], dp[i][j-1])

The additional constraint is handled separately:

Whenever we find matching characters where:

  • i belongs to word1
  • j belongs to word2

then dp[i][j] represents a palindrome that definitely uses characters from both strings, so we can update the answer.

This gives an efficient polynomial-time solution.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n × 2^m × (n+m)) O(n+m) Enumerates all subsequence pairs
Optimal Dynamic Programming O((n+m)^2) O((n+m)^2) Computes longest palindromic subsequences over intervals

Algorithm Walkthrough

Step 1: Concatenate the Strings

We create:

s = word1 + word2

This allows us to treat the problem as a single interval DP problem.

Let:

  • n = len(word1)
  • m = len(word2)
  • total = n + m

Indices:

  • [0, n-1] belong to word1
  • [n, total-1] belong to word2

Step 2: Define the DP State

We define:

dp[i][j]

to mean:

The length of the longest palindromic subsequence inside substring s[i:j+1].

This is a classic interval DP definition.

Step 3: Initialize Base Cases

Every single character is a palindrome of length 1:

dp[i][i] = 1

Step 4: Process Intervals by Length

We compute answers for increasingly larger substrings.

For each interval [i, j]:

  • If s[i] == s[j]:

  • These characters can form the outer pair of a palindrome.

  • So:

dp[i][j] = dp[i+1][j-1] + 2

  • Otherwise:

  • We skip one endpoint:

dp[i][j] = max(dp[i+1][j], dp[i][j-1])

Step 5: Track Valid Cross-String Palindromes

The problem requires using characters from both strings.

Therefore, whenever:

  • s[i] == s[j]
  • i < n
  • j >= n

we know:

  • the left character comes from word1
  • the right character comes from word2

So dp[i][j] represents a valid palindrome using both strings.

We update:

answer = max(answer, dp[i][j])

Step 6: Return the Result

After filling the DP table, answer contains the maximum valid palindrome length.

If no valid cross-string palindrome exists, answer remains 0.

Why it works

The DP recurrence correctly computes the longest palindromic subsequence for every interval because every optimal palindrome either:

  • uses both endpoints if they match, or
  • excludes one endpoint otherwise.

The additional cross-string check guarantees that the palindrome contains characters from both original strings. Since every valid palindrome must eventually include an outer matching pair crossing the boundary, checking those pairs is sufficient to ensure correctness.

Python Solution

class Solution:
    def longestPalindrome(self, word1: str, word2: str) -> int:
        s = word1 + word2
        n1 = len(word1)
        total = len(s)

        dp = [[0] * total for _ in range(total)]

        for i in range(total):
            dp[i][i] = 1

        answer = 0

        for length in range(2, total + 1):
            for i in range(total - length + 1):
                j = i + length - 1

                if s[i] == s[j]:
                    if length == 2:
                        dp[i][j] = 2
                    else:
                        dp[i][j] = dp[i + 1][j - 1] + 2

                    if i < n1 and j >= n1:
                        answer = max(answer, dp[i][j])
                else:
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])

        return answer

The implementation begins by concatenating the two input strings into a single string s. This simplifies the interval DP formulation because every palindrome can now be viewed as a subsequence inside one string.

The DP table is initialized with zeros, and every diagonal entry is set to 1 because a single character is always a palindrome.

The outer loop iterates over substring lengths from 2 up to the full string length. This ordering is important because dp[i][j] depends on smaller intervals such as dp[i+1][j-1].

When the endpoints match, we extend the palindrome from the inner interval. Special handling for length 2 avoids accessing an invalid inner interval.

Whenever a matching pair crosses from word1 into word2, we update the answer. This guarantees that the palindrome uses characters from both strings.

If the endpoints do not match, we inherit the best answer from either excluding the left endpoint or excluding the right endpoint.

Finally, the algorithm returns the maximum valid palindrome length found.

Go Solution

func longestPalindrome(word1 string, word2 string) int {
	s := word1 + word2
	n1 := len(word1)
	total := len(s)

	dp := make([][]int, total)
	for i := range dp {
		dp[i] = make([]int, total)
		dp[i][i] = 1
	}

	answer := 0

	for length := 2; length <= total; length++ {
		for i := 0; i+length-1 < total; i++ {
			j := i + length - 1

			if s[i] == s[j] {
				if length == 2 {
					dp[i][j] = 2
				} else {
					dp[i][j] = dp[i+1][j-1] + 2
				}

				if i < n1 && j >= n1 {
					if dp[i][j] > answer {
						answer = dp[i][j]
					}
				}
			} else {
				if dp[i+1][j] > dp[i][j-1] {
					dp[i][j] = dp[i+1][j]
				} else {
					dp[i][j] = dp[i][j-1]
				}
			}
		}
	}

	return answer
}

The Go implementation follows the same dynamic programming structure as the Python version. The main difference is explicit slice allocation for the two-dimensional DP table.

Go strings are byte indexed, which works correctly here because the input contains only lowercase English letters. No Unicode handling is required.

Since Go does not provide a built-in max function for integers, comparisons are handled manually with if statements.

Worked Examples

Example 1

word1 = "cacb"
word2 = "cbba"

Concatenated string:

s = "cacbcbba"

Indices:

Index Character
0 c
1 a
2 c
3 b
4 c
5 b
6 b
7 a

Boundary:

  • 0..3 belong to word1
  • 4..7 belong to word2

Important DP updates:

i j Characters dp[i][j] Cross Boundary
1 7 a,a 5 Yes
3 6 b,b 2 Yes
2 4 c,c 2 Yes

For interval [1,7]:

a ... a

The interior longest palindrome is "bcb" of length 3.

So:

dp[1][7] = 3 + 2 = 5

Result:

5

Constructed palindrome:

abcba

Example 2

word1 = "ab"
word2 = "ab"

Concatenated string:

s = "abab"

Important intervals:

i j Characters dp[i][j]
0 2 a,a 3
1 3 b,b 3

For [0,2]:

a b a

This gives palindrome length 3.

Result:

3

Example 3

word1 = "aa"
word2 = "bb"

Concatenated string:

s = "aabb"

There is no matching pair crossing the boundary.

No valid palindrome can use characters from both strings.

Result:

0

Complexity Analysis

Measure Complexity Explanation
Time O((n+m)^2) Every interval in the DP table is processed once
Space O((n+m)^2) The full DP table is stored

Let:

N = len(word1) + len(word2)

The DP table contains N × N states. Each state is computed in constant time using previously computed intervals. Therefore the total runtime is quadratic.

The space complexity is also quadratic because we store the entire interval DP table.

Test Cases

sol = Solution()

assert sol.longestPalindrome("cacb", "cbba") == 5  # provided example
assert sol.longestPalindrome("ab", "ab") == 3  # odd length palindrome
assert sol.longestPalindrome("aa", "bb") == 0  # impossible case

assert sol.longestPalindrome("a", "a") == 2  # smallest valid even palindrome
assert sol.longestPalindrome("a", "b") == 0  # smallest impossible case

assert sol.longestPalindrome("abc", "cba") == 6  # full mirrored strings
assert sol.longestPalindrome("abc", "def") == 0  # no shared characters

assert sol.longestPalindrome("aaaa", "aaaa") == 8  # all characters usable
assert sol.longestPalindrome("abca", "zaza") == 5  # mixed matching structure

assert sol.longestPalindrome("x", "xx") == 2  # repeated chars across boundary
assert sol.longestPalindrome("leetcode", "etco") == 5  # non-trivial subsequence

assert sol.longestPalindrome("bb", "bb") == 4  # full even palindrome
assert sol.longestPalindrome("abcde", "edcba") == 10  # maximum mirrored usage
Test Why
"cacb", "cbba" Verifies the main sample case
"ab", "ab" Tests odd-length palindrome
"aa", "bb" Tests impossible construction
"a", "a" Smallest successful input
"a", "b" Smallest failure input
"abc", "cba" Tests full mirrored palindrome
"abc", "def" Tests completely disjoint alphabets
"aaaa", "aaaa" Tests repeated-character behavior
"abca", "zaza" Tests subsequence flexibility
"x", "xx" Tests duplicate handling
"leetcode", "etco" Tests complex subsequence selection
"bb", "bb" Tests even-length palindrome
"abcde", "edcba" Tests maximal cross-boundary construction

Edge Cases

No Shared Characters Between Strings

If the two strings share no common characters, it is impossible to form a palindrome using both strings because every palindrome requires matching characters on both sides.

Example:

word1 = "abc"
word2 = "def"

The implementation correctly returns 0 because no cross-boundary matching pair is ever found.

Single Character Strings

Very small inputs can expose indexing bugs, especially with interval DP transitions involving dp[i+1][j-1].

Example:

word1 = "a"
word2 = "a"

The implementation handles this safely with the special case for substrings of length 2.

Palindrome Entirely Inside One String

A standard longest palindromic subsequence algorithm would incorrectly allow solutions entirely contained within one string.

Example:

word1 = "racecar"
word2 = "x"

The longest palindrome inside the concatenated string is "racecar" with length 7, but it does not use characters from word2.

The implementation avoids this bug by only updating the answer when the matching endpoints cross the boundary between the two original strings.