Skip to main content

Maximum Product of the Length of Two Palindromic Subsequences

Problem 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.

Examples​

Example 1: image

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 = "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.

Solution for Maximum Product of the Length of Two Palindromic Subsequences​

  1. Generate All Subsequences:

    • The function sub recursively generates all subsequences of the input string s.
    • For each subsequence, it checks if it is a palindrome using the isPalindrome function.
    • If a subsequence is a palindrome, it is added to the global result list ans.

  2. Check Palindromes:

    • The function isPalindrome takes a string and a list of indices (subsequence) and checks if the characters at these indices form a palindrome.

  3. Check Non-overlapping Subsequences:

    • The function check takes two subsequences and checks if they have any common elements (indices).
    • If they don't share any indices, they are considered non-overlapping.

  4. Calculate Maximum Product:

    • The function maxProduct iterates through all pairs of palindromic subsequences.
    • For each pair, it checks if they are non-overlapping using the check function.
    • If they are non-overlapping, it calculates the product of their lengths and updates the maximum product found.

Intuition​

  • The idea is to find all palindromic subsequences and then determine the maximum product of the lengths of two non-overlapping palindromic subsequences.
  • Generating all subsequences ensures that no potential palindromic subsequences are missed.
  • Checking for non-overlapping ensures that the two subsequences do not share any characters, thus making the product calculation valid.

Implementation​

Live Editor
function Solution(arr) {
        const ans = [];

    function isPalindrome(s, ans) {
        let a = 0, b = ans.length - 1;
        while (a <= b) {
            if (s[ans[a]] !== s[ans[b]]) return false;
            a++;
            b--;
        }
        return true;
    }

    function check(a, b) {
        for (let i = 0; i < a.length; i++) {
            for (let j = 0; j < b.length; j++) {
                if (a[i] === b[j]) return false;
            }
        }
        return true;
    }

    function sub(nums, i, temp) {
        if (isPalindrome(nums, temp)) ans.push([...temp]);
        if (i >= nums.length) return;

        temp.push(i);
        sub(nums, i + 1, temp);

        temp.pop();
        sub(nums, i + 1, temp);
    }

    function maxProduct(s) {
        const temp = [];
        sub(s, 0, temp);
        let res = 0;
        for (let i = 0; i < ans.length; i++) {
            for (let j = i + 1; j < ans.length; j++) {
                let x = ans[i].length * ans[j].length;
                if (check(ans[i], ans[j])) {
                    res = Math.max(res, x);
                }
            }
        }
        return res;
    }

  const input = "leetcodecom"
  const output = maxProduct(input)
  return (
    <div>
      <p>
        <b>Input: </b>
        {JSON.stringify(input)}
      </p>
      <p>
        <b>Output:</b> {output.toString()}
      </p>
    </div>
  );
}
Result
Loading...

Complexity Analysis​

  • Time Complexity: O(n∗4n)O(n * 4^n)
  • Space Complexity: O(n∗2n) O(n * 2^n)

Code in Different Languages​

Written by @hiteshgahanolia
const ans = [];

function isPalindrome(s, ans) {
 let a = 0, b = ans.length - 1;
 while (a <= b) {
     if (s[ans[a]] !== s[ans[b]]) return false;
     a++;
     b--;
 }
 return true;
}

function check(a, b) {
 for (let i = 0; i < a.length; i++) {
     for (let j = 0; j < b.length; j++) {
         if (a[i] === b[j]) return false;
     }
 }
 return true;
}

function sub(nums, i, temp) {
 if (isPalindrome(nums, temp)) ans.push([...temp]);
 if (i >= nums.length) return;

 temp.push(i);
 sub(nums, i + 1, temp);

 temp.pop();
 sub(nums, i + 1, temp);
}

function maxProduct(s) {
 const temp = [];
 sub(s, 0, temp);
 let res = 0;
 for (let i = 0; i < ans.length; i++) {
     for (let j = i + 1; j < ans.length; j++) {
         let x = ans[i].length * ans[j].length;
         if (check(ans[i], ans[j])) {
             res = Math.max(res, x);
         }
     }
 }
 return res;
}

References​