Maximum Product of the Length of Two Palindromic Subsequences

Given a string s, split its characters into two disjoint subsequences so that both subsequences are palindromes and the product of their lengths is maximized. Return the maximum product. Pattern focus: Longest palindromic subsequence. This problem combines subset enumeration with palindromic subsequence DP ideas.

Input Format

s = input string

Output Format

maximum product of the lengths of two palindromic subsequences

Constraints

  • 1 <= s.length <= 12
  • s contains lowercase English letters.

Examples

Example 1:

Input:

s = "leetcodecom"

Output:

9

Explanation:

This is a standard example where the best product is 9.

Example 2:

Input:

s = "bb"

Output:

1

Explanation:

Split into b and b, product = 1.

Loading...
Maximum Product of the Length of Two…