1771. Maximize Palindrome Length From Subsequences

Description

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.

 

Solutions

Solution: Dynamic Programming

• Time complexity: O(n²)
• Space complexity: O(n²)

 

JavaScript

/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
const longestPalindrome = function (word1, word2) {
  const m = word1.length;
  const word = `${word1}${word2}`;
  const n = word.length;
  const dp = Array.from({ length: n }, () => new Array(n).fill(0));
  let result = 0;

  for (let index = 0; index < n; index++) {
    dp[index][index] = 1;
  }

  for (let length = 2; length <= n; length++) {
    for (let start = 0; start + length - 1 < n; start++) {
      const end = start + length - 1;

      if (word[start] === word[end]) {
        dp[start][end] = dp[start + 1][end - 1] + 2;

        if (start < m && end >= m) {
          result = Math.max(dp[start][end], result);
        }
      } else {
        dp[start][end] = Math.max(dp[start + 1][end], dp[start][end - 1]);
      }
    }
  }

  return result;
};