2002. Maximum Product of the Length of Two Palindromic Subsequences

Description

Given a string s, find two disjoint palindromic subsequences of s such that the product of their lengths is maximized. The two subsequences are disjoint if they do not both pick a character at the same index.

Return the maximum possible product of the lengths of the two palindromic subsequences.

A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters. A string is palindromic if it reads the same forward and backward.

 

Example 1:

Input: s = "leetcodecom"
Output: 9
Explanation: An optimal solution is to choose "ete" for the 1st subsequence and "cdc" for the 2nd subsequence.
The product of their lengths is: 3 * 3 = 9.

Example 2:

Input: s = "bb"
Output: 1
Explanation: An optimal solution is to choose "b" (the first character) for the 1st subsequence and "b" (the second character) for the 2nd subsequence.
The product of their lengths is: 1 * 1 = 1.

Example 3:

Input: s = "accbcaxxcxx"
Output: 25
Explanation: An optimal solution is to choose "accca" for the 1st subsequence and "xxcxx" for the 2nd subsequence.
The product of their lengths is: 5 * 5 = 25.

 

Constraints:

• 2 <= s.length <= 12
• s consists of lowercase English letters only.

 

Solutions

Solution: Backtracking

• Time complexity: O(3ⁿ*n)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {string} s
 * @return {number}
 */
const maxProduct = function (s) {
  const sub1 = [];
  const sub2 = [];
  const size = s.length;
  let result = 0;

  findMaxProduct();
  return result;

  function findMaxProduct(index = 0) {
    if (index >= size) {
      if (isPalindromic(sub1) && isPalindromic(sub2)) {
        result = Math.max(sub1.length * sub2.length, result);
      }
      return;
    }
    const char = s[index];

    sub1.push(char);
    findMaxProduct(index + 1);
    sub1.pop();
    sub2.push(char);
    findMaxProduct(index + 1);
    sub2.pop();
    findMaxProduct(index + 1);
  }
  function isPalindromic(sub) {
    if (!sub.length) return false;
    let left = 0;
    let right = sub.length - 1;

    while (left < right) {
      if (sub[left++] !== sub[right--]) return false;
    }
    return true;
  }
};