Maximum Product of the Length of Two Palindromic Subsequences
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.
Example 1
Input
s = "leetcodecom"Output
9An optimal solution is to choose
ete for the 1st subsequence and cdc for the 2nd subsequence, giving a product of 3 * 3 = 9.Example 2
Input
s = "bb"Output
1An optimal solution is to choose
b from each index, giving a product of 1 * 1 = 1.Constraints
- 2 <= s.length <= 12
- s consists of lowercase English letters only.
Asked at 2 companies
Practice questions like this out loud in a mock coding interview with a live AI interviewer. First one free.