Move from brute-force thinking to an efficient approach using dynamic programming strategy.
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: 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.
Constraints:
2 <= s.length <= 12s consists of lowercase English letters only.Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Dynamic Programming · Backtracking · Bit Manipulation
"leetcodecom"
"bb"
"accbcaxxcxx"
valid-palindrome)longest-palindromic-subsequence)maximum-product-of-the-length-of-two-palindromic-substrings)maximum-points-in-an-archery-competition)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #2002: Maximum Product of the Length of Two Palindromic Subsequences
class Solution {
public int maxProduct(String s) {
int n = s.length();
boolean[] p = new boolean[1 << n];
Arrays.fill(p, true);
for (int k = 1; k < 1 << n; ++k) {
for (int i = 0, j = n - 1; i < n; ++i, --j) {
while (i < j && (k >> i & 1) == 0) {
++i;
}
while (i < j && (k >> j & 1) == 0) {
--j;
}
if (i < j && s.charAt(i) != s.charAt(j)) {
p[k] = false;
break;
}
}
}
int ans = 0;
for (int i = 1; i < 1 << n; ++i) {
if (p[i]) {
int a = Integer.bitCount(i);
int mx = ((1 << n) - 1) ^ i;
for (int j = mx; j > 0; j = (j - 1) & mx) {
if (p[j]) {
int b = Integer.bitCount(j);
ans = Math.max(ans, a * b);
}
}
}
}
return ans;
}
}
// Accepted solution for LeetCode #2002: Maximum Product of the Length of Two Palindromic Subsequences
func maxProduct(s string) (ans int) {
n := len(s)
p := make([]bool, 1<<n)
for i := range p {
p[i] = true
}
for k := 1; k < 1<<n; k++ {
for i, j := 0, n-1; i < j; i, j = i+1, j-1 {
for i < j && (k>>i&1) == 0 {
i++
}
for i < j && (k>>j&1) == 0 {
j--
}
if i < j && s[i] != s[j] {
p[k] = false
break
}
}
}
for i := 1; i < 1<<n; i++ {
if p[i] {
a := bits.OnesCount(uint(i))
mx := (1<<n - 1) ^ i
for j := mx; j > 0; j = (j - 1) & mx {
if p[j] {
b := bits.OnesCount(uint(j))
ans = max(ans, a*b)
}
}
}
}
return
}
# Accepted solution for LeetCode #2002: Maximum Product of the Length of Two Palindromic Subsequences
class Solution:
def maxProduct(self, s: str) -> int:
n = len(s)
p = [True] * (1 << n)
for k in range(1, 1 << n):
i, j = 0, n - 1
while i < j:
while i < j and (k >> i & 1) == 0:
i += 1
while i < j and (k >> j & 1) == 0:
j -= 1
if i < j and s[i] != s[j]:
p[k] = False
break
i, j = i + 1, j - 1
ans = 0
for i in range(1, 1 << n):
if p[i]:
mx = ((1 << n) - 1) ^ i
j = mx
a = i.bit_count()
while j:
if p[j]:
b = j.bit_count()
ans = max(ans, a * b)
j = (j - 1) & mx
return ans
// Accepted solution for LeetCode #2002: Maximum Product of the Length of Two Palindromic Subsequences
impl Solution {
pub fn max_product(s: String) -> i32 {
let s: Vec<char> = s.chars().collect();
let mut s1 = vec![];
let mut s2 = vec![];
let mut res = 0;
Solution::dfs(&s, &mut s1, &mut s2, &mut res, 0);
res
}
fn dfs(s: &[char], s1: &mut Vec<char>, s2: &mut Vec<char>, res: &mut i32, index: usize) {
// Base case
if index == s.len() {
if Solution::is_palindrome(s1) && Solution::is_palindrome(s2) {
let new_max = s1.len() * s2.len();
*res = std::cmp::max(*res, new_max as i32);
}
return;
}
// Option 0: Not in S1 nor S2
Solution::dfs(s, s1, s2, res, index + 1);
// Option 1: in S1
s1.push(s[index]);
Solution::dfs(s, s1, s2, res, index + 1);
s1.pop();
// Option 2: in S2
s2.push(s[index]);
Solution::dfs(s, s1, s2, res, index + 1);
s2.pop();
}
fn is_palindrome(s: &[char]) -> bool {
if s.len() <= 1 {
return true;
}
let mut l = 0;
let mut r = s.len() - 1;
while l < r {
if s[l] != s[r] {
return false;
}
l += 1;
r -= 1;
}
true
}
}
// Accepted solution for LeetCode #2002: Maximum Product of the Length of Two Palindromic Subsequences
/**
* Time Complexity: O(2^N)
* Space Complexity: O(2^N)
*/
function maxProduct(s: string): number {
const N = s.length;
const first: number[] = new Array(1 << N).fill(0),
last: number[] = new Array(1 << N).fill(0);
for (let i = 0; i < N; i++) {
for (let j = 1 << i; j < 1 << (i + 1); j++) {
first[j] = i;
}
}
for (let i = 0; i < N; i++) {
for (let j = 1 << i; j < 1 << N; j += 1 << (i + 1)) {
last[j] = i;
}
}
const dp = cache((m: number) => {
if ((m & (m - 1)) === 0) {
return m != 0;
}
const l = last[m],
f = first[m];
const lb = 1 << l,
fb = 1 << f;
return Math.max(
dp(m - lb),
dp(m - fb),
dp(m - lb - fb) + Number(s[l] === s[f]) * 2,
);
});
let ans = 0;
for (let m = 1; m < 1 << N; m++) {
ans = Math.max(ans, dp(m) * dp((1 << N) - 1 - m));
}
return ans;
}
function cache(func: Function) {
const map = new Map();
var wrapper = (m: number) => {
if (!map.get(m)) {
map.set(m, func(m));
}
return map.get(m);
};
return wrapper;
}
Use this to step through a reusable interview workflow for this problem.
Pure recursion explores every possible choice at each step. With two choices per state (take or skip), the decision tree has 2ⁿ leaves. The recursion stack uses O(n) space. Many subproblems are recomputed exponentially many times.
Each cell in the DP table is computed exactly once from previously solved subproblems. The table dimensions determine both time and space. Look for the state variables — each unique combination of state values is one cell. Often a rolling array can reduce space by one dimension.
Review these before coding to avoid predictable interview regressions.
Wrong move: An incomplete state merges distinct subproblems and caches incorrect answers.
Usually fails on: Correctness breaks on cases that differ only in hidden state.
Fix: Define state so each unique subproblem maps to one DP cell.
Wrong move: Mutable state leaks between branches.
Usually fails on: Later branches inherit selections from earlier branches.
Fix: Always revert state changes immediately after recursive call.