2002. Maximum Product of the Length of Two Palindromic Subsequences (Medium) - TengnanYao/daily_leetcode GitHub Wiki

class Solution:
    def maxProduct(self, s: str) -> int:
        n = len(s)
        combs = set()
        def dfs(cur, i, arr):
            if cur == cur[ : : -1]:
                combs.add(tuple(arr))
            if i < n:
                dfs(cur, i + 1, arr)
                dfs(cur + s[i], i + 1, arr + [i])
        dfs("", 0, [])
        result = 0
        combs = list(combs)
        m = (n // 2) * (n - n // 2)
        for i in range(len(combs)):
            for j in range(i + 1, len(combs)):
                length = len(combs[i]) * len(combs[j])
                if length > result:
                    if not set(combs[i]) & set(combs[j]):
                        result = length
                        if length == m:
                            return result
        return result