Maximum product of the length of two palindromic subsequences

String Dynamic Programming Backtracking Bit Manipulation Bitmask

62.4% acceptance

Feb 25, 2026

1014

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 share any indices in s. Return the maximum possible product of the lengths of the two palindromic subsequences.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn max_product(s: String) -> i32 {
    let n = s.len();
    let s: Vec<u8> = s.bytes().collect();
    let total = 1 << n;
    // Precompute palindrome length for each subset
    let mut pal = vec![0usize; total];
    for mask in 1..total {
      let chars: Vec<u8> = (0..n).filter(|&i| mask & (1 << i) != 0).map(|i| s[i]).collect();
      pal[mask] = longest_palindrome_len(&chars);
    }
    let mut ans = 0;
    // Enumerate pairs of disjoint subsets
    let full = total - 1;
    let mut sub = full;
    loop {
      let comp = full ^ sub;
      if comp != 0 && sub != 0 {
        let prod = pal[sub] * pal[comp];
        if prod > ans { ans = prod; }
      }
      if sub == 0 { break; }
      sub = (sub - 1) & full;
    }
    ans as i32
  }
}

fn longest_palindrome_len(s: &[u8]) -> usize {
  let n = s.len();
  if n == 0 { return 0; }
  let mut dp = vec![vec![0usize; n]; n];
  for i in 0..n { dp[i][i] = 1; }
  for len in 2..=n {
    for i in 0..=(n - len) {
      let j = i + len - 1;
      if s[i] == s[j] {
        dp[i][j] = if len == 2 { 2 } else { dp[i+1][j-1] + 2 };
      } else {
        dp[i][j] = dp[i+1][j].max(dp[i][j-1]);
      }
    }
  }
  dp[0][n-1]
}