Maximize Palindrome Length From Subsequences

You are given two strings word1 and word2. You want to construct a string by selecting a subsequence from word1 and a subsequence from word2, then concatenating them. The goal is to make that concatenated string a palindrome. You must use at least one character from word1 and at least one from word2. Return the length of the longest palindrome you can build this way, or 0 if it is impossible.

This is LeetCode 1771: Maximize Palindrome Length From Subsequences. It looks like a brand-new problem at first, but the core is something you already know: the Longest Palindromic Subsequence. The twist is that your palindrome must span two strings, pulling characters from both.

Why this problem matters

LPS on a single string is a classic interval DP exercise. This problem forces you to extend that technique to a setting with constraints. You cannot just find the longest palindromic subsequence of the combined string and call it done. You need to guarantee that the palindrome actually uses characters from both halves. That extra constraint is what makes this a hard problem instead of a medium one.

In interviews, this pattern shows up whenever you need to run a known DP algorithm on a modified input while enforcing an external condition. If you can handle LPS with a boundary constraint, you can handle similar variations on LCS, edit distance, and other two-string DP problems.

The key insight

Concatenate word1 and word2 into a single string s = word1 + word2. Now run the standard LPS interval DP on s. The DP table dp[i][j] gives the longest palindromic subsequence of s[i..j].

But you do not just want dp[0][len(s)-1]. You need the palindrome to include at least one character from word1 (the first n1 characters of s) and at least one from word2 (the last n2 characters of s). The trick is to track the answer during the DP fill. Whenever you find a match where s[i] == s[j] with i in the word1 range (i < n1) and j in the word2 range (j >= n1), you know that palindrome uses at least one character from each word. Update the result with dp[i][j].

The solution

def longest_palindrome(word1, word2):
    s = word1 + word2
    n = len(s)
    n1 = len(word1)
    dp = [[0] * n for _ in range(n)]
    result = 0

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

    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                dp[i][j] = dp[i + 1][j - 1] + 2
                if i < n1 and j >= n1:
                    result = max(result, dp[i][j])
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])

    return result

The outer loop iterates over substring lengths from 2 up to n. For each length, the inner loop considers every starting index i. When s[i] == s[j], we extend the palindrome by wrapping those two characters around dp[i+1][j-1]. When they do not match, we take the better of dropping the left character or dropping the right character. The result variable only gets updated when a matching pair crosses the boundary between word1 and word2.

Visual walkthrough

In this example, word1 = "ab" and word2 = "ba", so s = "abba". The standard LPS of "abba" is 4 (the entire string). The cross-boundary check catches this at dp[0][3] because s[0] = 'a' is in word1 and s[3] = 'a' is in word2. It also catches dp[1][2] where s[1] = 'b' is in word1 and s[2] = 'b' is in word2, giving a palindrome of length 2. The answer is 4.

Complexity analysis

Where n = len(word1) and m = len(word2). The DP table is (n+m) x (n+m), and we fill roughly half of it (the upper triangle).

The building blocks

1. Longest Palindromic Subsequence (interval DP)

The core algorithm that makes everything work. Given a string s, dp[i][j] stores the LPS of s[i..j].

def lps(s):
    n = len(s)
    dp = [[0] * n for _ in range(n)]

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

    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                dp[i][j] = dp[i + 1][j - 1] + 2
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])

    return dp[0][n - 1]

This is the standard LPS you should know cold. The only change for our problem is concatenating two strings first and tracking cross-boundary matches.

2. Cross-boundary tracking

The constraint that the palindrome must use characters from both words translates to: when s[i] == s[j], check if i is in the word1 range and j is in the word2 range.

if s[i] == s[j]:
    dp[i][j] = dp[i + 1][j - 1] + 2
    if i < len(word1) and j >= len(word1):
        result = max(result, dp[i][j])

This is the only addition to the standard LPS algorithm. It costs nothing in terms of time or space complexity, just a single comparison and a max update.

Edge cases

• No common character: if word1 and word2 share no character in common, no cross-boundary palindrome exists. The result stays 0. For example, word1 = "aa" and word2 = "bb" returns 0.
• Single character each: word1 = "a" and word2 = "a" gives s = "aa", and dp[0][1] = 2. Since s[0] is in word1 and s[1] is in word2, the answer is 2.
• One string empty in spirit: the problem guarantees both strings have length at least 1, so you do not need to handle truly empty inputs.
• Entire concatenation is a palindrome: word1 = "ab" and word2 = "ba" gives s = "abba". The full LPS is 4, and the outermost matching pair crosses the boundary. Answer is 4.

From understanding to recall

The pattern here is clean: take a known algorithm (LPS), run it on a modified input (concatenated strings), and add a constraint check during the fill (cross-boundary match). Recognizing that pattern is the hard part. Once you see that concatenation turns two strings into one, the rest is standard interval DP with a single if guard.

To solidify this, practice identifying when a problem can be reduced to a known DP by reshaping the input. LeetCode 1771 is a concatenation reduction. Other problems use reversal (LPS as LCS of s and reverse(s)), interleaving, or padding. The underlying DP is always something you already know.

Related posts

• Longest Palindromic Subsequence - the foundational interval DP that this problem extends
• Longest Palindromic Substring - contiguous variant, different approach but same palindrome intuition
• Edit Distance - another classic 2D string DP with a similar table structure

If you want to build lasting fluency with palindrome DP and other string problems, CodeBricks uses spaced repetition to move these patterns from short-term cramming into long-term recall. Instead of solving LeetCode 1771 once and forgetting the boundary trick, you revisit it at optimally spaced intervals until the reduction is automatic.