Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

2130. Maximum Product of the Length of Two Palindromic Subsequences

My accepted Python solution to LeetCode problem 2130, Maximum Product of the Length of Two Palindromic Subsequences, running in 762ms.

  • Difficulty: Medium
  • Python
  • Runtime 762ms
  • Memory 17.7MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 762ms, memory 17.7MB, accepted 2025-12-29.

python
class Solution:
    def maxProduct(self, s: str) -> int:
        n = len(s)
        
        def isPalindrome(mask):
            chars = [s[i] for i in range(n) if mask & (1 << i)]
            return chars == chars[::-1]
        
        # Pre-compute palindrome lengths for all masks
        pal_len = {}
        for mask in range(1, 1 << n):
            if isPalindrome(mask):
                pal_len[mask] = bin(mask).count('1')
        
        max_product = 0
        masks = list(pal_len.keys())
        
        for i, m1 in enumerate(masks):
            for m2 in masks[i+1:]:
                if m1 & m2 == 0:  # Disjoint
                    max_product = max(max_product, pal_len[m1] * pal_len[m2])
        
        return max_product

Source