Maximize Palindrome Length From Subsequences

Hard
1515.

Maximize Palindrome Length From Subsequences

Maximize Palindrome Length From Subsequences is a hard coding problem on strings and dynamic programming, asked in Amazon and Google interviews.

You are given two strings word1 and word2. Build a string as follows: choose a non-empty subsequence sub1 of word1 and a non-empty subsequence sub2 of word2, then concatenate them as sub1 + sub2.

Return the length of the longest palindrome that can be built this way. If no palindrome can be built, return 0.

A subsequence keeps the original order of the characters it uses but may skip any of them; a palindrome reads the same forwards and backwards.

Example 1

Input
word1 = "code", word2 = "kairo"
Output
3
Explanation
Take `"od"` from `word1` and `"o"` from `word2` to get `"odo"`. The only letter both words share is `o`.

Example 2

Input
word1 = "abc", word2 = "cba"
Output
6
Explanation
Use both words whole: `"abccba"`.

Example 3

Input
word1 = "aa", word2 = "bb"
Output
0
Explanation
A palindrome would need its first character (from `word1`) to equal its last (from `word2`).

Constraints

  • 1 <= word1.length, word2.length <= 1000
  • word1 and word2 consist of lowercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var longestPalindrome = function(word1, word2) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximize Palindrome Length From Subsequences — Solution

Maximize Palindrome Length From Subsequences solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Maximize Palindrome Length From Subsequences is a hard coding problem on strings and dynamic programming, asked in Amazon and Google interviews.

  • Difficulty: Hard
  • Topics: Strings, Dynamic Programming
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given two strings word1 and word2. Build a string as follows: choose a non-empty subsequence sub1 of word1 and a non-empty subsequence sub2 of word2, then concatenate them as sub1 + sub2.

Return the length of the longest palindrome that can be built this way. If no palindrome can be built, return 0.

A subsequence keeps the original order of the characters it uses but may skip any of them; a palindrome reads the same forwards and backwards.

Example 1

Input: word1 = "code", word2 = "kairo"
Output: 3
Explanation: Take `"od"` from `word1` and `"o"` from `word2` to get `"odo"`. The only letter both words share is `o`.

Example 2

Input: word1 = "abc", word2 = "cba"
Output: 6
Explanation: Use both words whole: `"abccba"`.

Example 3

Input: word1 = "aa", word2 = "bb"
Output: 0
Explanation: A palindrome would need its first character (from `word1`) to equal its last (from `word2`).

Constraints

  • 1 <= word1.length, word2.length <= 1000
  • word1 and word2 consist of lowercase English letters

Hints for Maximize Palindrome Length From Subsequences

  1. Hint 1

    Join the words: s = word1 + word2. Any built string is a subsequence of s that uses at least one character on each side of the seam.

  2. Hint 2

    In a palindrome the first and last characters match. Here the first comes from word1 and the last from word2 — so the outermost matched pair must straddle the seam.

  3. Hint 3

    Compute the longest palindromic subsequence table dp[i][j] of s. Whenever s[i] == s[j] with i in word1 and j in word2, dp[i][j] = dp[i+1][j-1] + 2 is a candidate; take the maximum.

How to solve Maximize Palindrome Length From Subsequences

A palindrome built from sub1 + sub2 is a palindromic subsequence of s = word1 + word2 whose first character lies in word1 and whose last lies in word2 — and those two characters are equal. So run the standard longest-palindromic-subsequence DP on s and only accept answers whose outer pair crosses the seam.

Approach

  1. Let s = word1 + word2 and n1 = len(word1).
  2. Fill dp[i][j], the longest palindromic subsequence of s[i..j], for i from the end down and j upward: dp[i][i] = 1; if s[i] == s[j] then dp[i][j] = dp[i+1][j-1] + 2, else max(dp[i+1][j], dp[i][j-1]).
  3. Whenever s[i] == s[j] with i < n1 <= j, update the answer with dp[i][j].
  4. Return the answer (0 if no such pair exists).

Why it works

If a valid palindrome exists, its outermost characters are equal, sit at some i < n1 <= j, and the inside is a palindromic subsequence of s[i+1..j-1], so its length is at most dp[i+1][j-1] + 2. Conversely, for any such equal pair, the pair plus a longest palindromic subsequence of the inside is a valid build — the outer characters guarantee both parts are non-empty, and the inside may use either word freely. So the maximum over straddling equal pairs is exactly the answer.

Complexity

  • Time — O((m + n)^2)
  • Space — O((m + n)^2)

Pitfalls

  • Taking the longest palindromic subsequence of s overall is wrong — it may lie entirely inside one word.
  • Only pairs with s[i] == s[j] may be the outer pair; a max(...) entry is not anchored at i and j.
  • If no letter occurs in both words, the answer is 0.

Reference solution

Python

def longestPalindrome(word1: str, word2: str) -> int:
    s = word1 + word2
    n, n1 = len(s), len(word1)
    dp = [[0] * n for _ in range(n)]
    best = 0
    for i in range(n - 1, -1, -1):
        dp[i][i] = 1
        for j in range(i + 1, n):
            if s[i] == s[j]:
                dp[i][j] = dp[i + 1][j - 1] + 2
                if i < n1 <= j and dp[i][j] > best:
                    best = dp[i][j]
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
    return best

Java

public static int longestPalindrome(String word1, String word2) {
    String s = word1 + word2;
    int n = s.length(), n1 = word1.length();
    int[][] dp = new int[n][n];
    int best = 0;
    for (int i = n - 1; i >= 0; i--) {
        dp[i][i] = 1;
        for (int j = i + 1; j < n; j++) {
            if (s.charAt(i) == s.charAt(j)) {
                dp[i][j] = dp[i + 1][j - 1] + 2;
                if (i < n1 && j >= n1 && dp[i][j] > best) best = dp[i][j];
            } else {
                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }
    return best;
}

C++

int longestPalindrome(string word1, string word2) {
    string s = word1 + word2;
    int n = s.size(), n1 = word1.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    int best = 0;
    for (int i = n - 1; i >= 0; i--) {
        dp[i][i] = 1;
        for (int j = i + 1; j < n; j++) {
            if (s[i] == s[j]) {
                dp[i][j] = dp[i + 1][j - 1] + 2;
                if (i < n1 && j >= n1 && dp[i][j] > best) best = dp[i][j];
            } else {
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }
    return best;
}

JavaScript

var longestPalindrome = function(word1, word2) {
    var s = word1 + word2, n = s.length, n1 = word1.length;
    var dp = [];
    for (var i = 0; i < n; i++) dp.push(new Array(n).fill(0));
    var best = 0;
    for (var i = n - 1; i >= 0; i--) {
        dp[i][i] = 1;
        for (var j = i + 1; j < n; j++) {
            if (s[i] === s[j]) {
                dp[i][j] = dp[i + 1][j - 1] + 2;
                if (i < n1 && j >= n1 && dp[i][j] > best) best = dp[i][j];
            } else {
                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Dynamic Programming