maximum-product-of-the-length-of-two-palindromic-subsequences

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

Given a string <code>s</code>, find two disjoint palindromic subsequences of <code>s</code> 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.

&nbsp;
Example 1:
<img alt="example-1" src="https://assets.leetcode.com/uploads/2021/08/24/two-palindromic-subsequences.png" style="width: 550px; height: 124px;" />
<pre>
Input: s = &quot;leetcodecom&quot;
Output: 9
Explanation: An optimal solution is to choose &quot;ete&quot; for the 1st subsequence and &quot;cdc&quot; for the 2nd subsequence.
The product of their lengths is: 3 * 3 = 9.
</pre>

Example 2:

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

Example 3:

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

&nbsp;
Constraints:

<ul>
	<li><code>2 &lt;= s.length &lt;= 12</code></li>
	<li><code>s</code> consists of lowercase English letters only.</li>
</ul>

maxProduct

Maximum Product of the Length of Two Palindromic Subsequences

Valid Palindrome

valid-palindrome

验证回文串

Longest Palindromic Subsequence

longest-palindromic-subsequence

最长回文子序列

Maximum Product of the Length of Two Palindromic Substrings

maximum-product-of-the-length-of-two-palindromic-substrings

两个回文子字符串长度的最大乘积

Maximum Points in an Archery Competition

maximum-points-in-an-archery-competition

射箭比赛中的最大得分

Bit Manipulation

String

Dynamic Programming

Backtracking

Bitmask

给你一个字符串&nbsp;<code>s</code>&nbsp;，请你找到&nbsp;<code>s</code>&nbsp;中两个&nbsp;不相交回文子序列&nbsp;，使得它们长度的&nbsp;乘积最大&nbsp;。两个子序列在原字符串中如果没有任何相同下标的字符，则它们是&nbsp;不相交&nbsp;的。

请你返回两个回文子序列长度可以达到的&nbsp;最大乘积&nbsp;。

子序列&nbsp;指的是从原字符串中删除若干个字符（可以一个也不删除）后，剩余字符不改变顺序而得到的结果。如果一个字符串从前往后读和从后往前读一模一样，那么这个字符串是一个 回文字符串&nbsp;。

&nbsp;

示例 1：

<img alt="example-1" src="https://assets.leetcode.com/uploads/2021/08/24/two-palindromic-subsequences.png" style="width: 550px; height: 124px;">

<pre>输入：s = "leetcodecom"
输出：9
解释：最优方案是选择 "ete" 作为第一个子序列，"cdc" 作为第二个子序列。
它们的乘积为 3 * 3 = 9 。
</pre>

示例 2：

<pre>输入：s = "bb"
输出：1
解释：最优方案为选择 "b" （第一个字符）作为第一个子序列，"b" （第二个字符）作为第二个子序列。
它们的乘积为 1 * 1 = 1 。
</pre>

示例 3：

<pre>输入：s = "accbcaxxcxx"
输出：25
解释：最优方案为选择 "accca" 作为第一个子序列，"xxcxx" 作为第二个子序列。
它们的乘积为 5 * 5 = 25 。
</pre>

&nbsp;

提示：

<ul>
	<li><code>2 &lt;= s.length &lt;= 12</code></li>
	<li><code>s</code>&nbsp;只含有小写英文字母。</li>
</ul>