leetcode

# 2002. 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 maximised. 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 none of its characters without changing the ordering of the remaining
characters. a string is palindromic if it reads the same forward and backward
"""


class Solution(object):
    def maxProduct(self, s):
        """
        :type s: str
        :rtype: int
        """
        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

        def dp(m):
            if m & (m - 1) == 0:
                return m != 0
            f, l = first[m], last[m]
            fb, lb = 1 << f, 1 << l
            return max(dp(m - lb), dp(m - fb), dp(m - lb - fb) + (s[l] == s[f]) * 2)

        ans = 0
        for i in range(1, 1 << n):
            ans = max(ans, dp(i) * dp((1 << n) - 1 - i))
        return ans


if __name__ == "__main__":
    obj = Solution()
    print(obj.maxProduct(s="leetcodecom"))
    print(obj.maxProduct(s="bb"))
    print(obj.maxProduct(s="accbcaxxcxx"))