#2002
Maximum Product of the Length of Two Palindromic Subsequences
specialist · 680 · lc medium +30 · verified · 62.4% accepted · 1,014 likes · top 64%
Description
Given a string s, choose two non-overlapping palindromic subsequences — they are disjoint when no character index is selected by both. Maximize the product of their lengths and return that maximum.
A subsequence is obtained by removing zero or more characters while keeping the rest in order; a palindrome reads identically forwards and backwards.
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.
Code
1
2
3