Problem statement

https://leetcode.com/problems/maximum-product-of-the-length-of-two-palindromic-subsequences/

Solution

I saw several dp solution, which states that they have O(2^n) complexity, but they use bit manipulations, such as looking for first and last significant bit, which we can not say is truly O(1). So I decided to write my own true O(2^n) solution.

Let dp(mask) be the maximum length of palindrome if we allowed to use only non-zero bits from mask. In fact, this means, if we have s = leetcode and mask = 01011001, we can use only etce subsequence. How to evaluate dp(mask)?

  1. First option is we do not take last significant one, that is we work here with 01011000 and ask what is answer for this mask.
  2. Second option is we do not take first significant bit, that is we work here with 00011001 mask here.
  3. Final option is to take both first and last significant bits but it is allowed only if we have equal elements for them, that is we have mase 00011000 here and because s[1] = s[7] we can take this option.

Also what I calclate all first and last significant bits for all numbers in range 1, 1<<n.

Complexity

Time complexity is O(2^n), space complexity also O(2^n) to keep dp cache and last and first arrays.

class Solution:
    def maxProduct(self, s):
        n = len(s)
        
        first, last = [0]*(1<<n), [0]*(1<<n)
        
        for i in range(n):
            for j in range(1<<i, 1<<(i+1)):
                first[j] = i

        for i in range(n):
            for j in range(1<<i, 1<<n, 1<<(i+1)):
                last[j] = i
        
        @lru_cache(None)
        def dp(m):
            if m & (m-1) == 0: return m != 0
            l, f = last[m], first[m]
            lb, fb = 1<<l, 1<<f
            return max(dp(m-lb), dp(m-fb), dp(m-lb-fb) + (s[l] == s[f]) * 2)
       
        ans = 0
        for m in range(1, 1<<n):
            ans = max(ans, dp(m)*dp((1<<n) - 1 - m))
            
        return ans