Package g2001_2100.s2002_maximum_product_of_the_length_of_two_palindromic_subsequences

Class Solution

java.lang.Object

g2001_2100.s2002_maximum_product_of_the_length_of_two_palindromic_subsequences.Solution

public class Solution
extends Object

2002 - Maximum Product of the Length of Two Palindromic Subsequences.<p>Medium</p> <p>Given a string <code>s</code>, find two <strong>disjoint palindromic subsequences</strong> of <code>s</code> such that the <strong>product</strong> of their lengths is <strong>maximized</strong>. The two subsequences are <strong>disjoint</strong> if they do not both pick a character at the same index.</p> <p>Return <em>the <strong>maximum</strong> possible <strong>product</strong> of the lengths of the two palindromic subsequences</em>.</p> <p>A <strong>subsequence</strong> 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 <strong>palindromic</strong> if it reads the same forward and backward.</p> <p><strong>Example 1:</strong></p> <p><img src="https://assets.leetcode.com/uploads/2021/08/24/two-palindromic-subsequences.png" alt="example-1" /></p> <p><strong>Input:</strong> s = &ldquo;leetcodecom&rdquo;</p> <p><strong>Output:</strong> 9</p> <p><strong>Explanation:</strong> An optimal solution is to choose &ldquo;ete&rdquo; for the 1^st subsequence and &ldquo;cdc&rdquo; for the 2^nd subsequence.</p> <p>The product of their lengths is: 3 * 3 = 9.</p> <p><strong>Example 2:</strong></p> <p><strong>Input:</strong> s = &ldquo;bb&rdquo;</p> <p><strong>Output:</strong> 1</p> <p><strong>Explanation:</strong> An optimal solution is to choose &ldquo;b&rdquo; (the first character) for the 1^st subsequence and &ldquo;b&rdquo; (the second character) for the 2^nd subsequence.</p> <p>The product of their lengths is: 1 * 1 = 1.</p> <p><strong>Example 3:</strong></p> <p><strong>Input:</strong> s = &ldquo;accbcaxxcxx&rdquo;</p> <p><strong>Output:</strong> 25</p> <p><strong>Explanation:</strong> An optimal solution is to choose &ldquo;accca&rdquo; for the 1^st subsequence and &ldquo;xxcxx&rdquo; for the 2^nd subsequence.</p> <p>The product of their lengths is: 5 * 5 = 25.</p> <p><strong>Constraints:</strong></p> <ul> <li><code>2 <= s.length <= 12</code></li> <li><code>s</code> consists of lowercase English letters only.</li> </ul>

Constructor Summary

Constructors

Constructor	Description
Solution()

Method Summary

Modifier and Type	Method	Description
int	maxProduct(String s)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

Solution

public Solution()

Method Details

maxProduct

public int maxProduct(String s)