2002. Maximum Product of The Length of Two Palindromic Subsequences - Explanation

class Solution:
    def maxProduct(self, s: str) -> int:
        def isPal(s):
            i, j = 0, len(s) - 1
            while i < j:
                if s[i] != s[j]:
                    return False
                i += 1
                j -= 1
            return True

        res = 0
        def rec(i, seq1, seq2):
            nonlocal res
            if i == len(s):
                if isPal(seq1) and isPal(seq2):
                    res = max(res, len(seq1) * len(seq2))
                return

            rec(i + 1, seq1, seq2)
            rec(i + 1, seq1 + s[i], seq2)
            rec(i + 1, seq1, seq2 + s[i])

        rec(0, "", "")
        return res

class Solution:
    def maxProduct(self, s: str) -> int:
        def isPal(s):
            i, j = 0, len(s) - 1
            while i < j:
                if s[i] != s[j]:
                    return False
                i += 1
                j -= 1
            return True

        N, pali = len(s), {}

        for mask in range(1, 1 << N):
            subseq = ""
            for i in range(N):
                if mask & (1 << i):
                    subseq += s[i]

            if isPal(subseq):
                pali[mask] = len(subseq)

        res = 0
        for m1 in pali:
            for m2 in pali:
                if m1 & m2 == 0:
                    res = max(res, pali[m1] * pali[m2])

        return res

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)
        if n == 0:
            return 0

        dp = [1] * n
        for i in range(n - 1, -1, -1):
            prev = 0
            for j in range(i + 1, n):
                tmp = dp[j]
                if s[i] == s[j]:
                    dp[j] = 2 + prev
                else:
                    dp[j] = max(dp[j - 1], dp[j])
                prev = tmp
        return dp[n - 1]

    def maxProduct(self, s: str) -> int:
        n = len(s)
        res = 0

        for i in range(1, 1 << n):
            seq1, seq2 = [], []

            for j in range(n):
                if (i & (1 << j)) != 0:
                    seq1.append(s[j])
                else:
                    seq2.append(s[j])

            if not self.isPal(seq1):
                continue

            lps = self.longestPalindromeSubseq(''.join(seq2))
            res = max(res, len(seq1) * lps)

        return res

    def isPal(self, s: str) -> bool:
        i, j = 0, len(s) - 1
        while i < j:
            if s[i] != s[j]:
                return False
            i += 1
            j -= 1
        return True

class Solution:
    def longestPalindromeSubseq(self, s: str, mask: int, dp: List[int]) -> int:
        n = len(s)
        for i in range(n - 1, -1, -1):
            if (mask & (1 << i)) != 0:
                continue

            prev = 0
            for j in range(i + 1, n):
                tmp = dp[j]
                if (mask & (1 << j)) == 0 and s[i] == s[j]:
                    dp[j] = 2 + prev
                else:
                    dp[j] = max(dp[j - 1], dp[j])
                prev = tmp
        return dp[-1]

    def maxProduct(self, s: str) -> int:
        n = len(s)
        res = 0
        dp = [1] * n

        for i in range(1, 1 << n):
            m1 = self.palsize(s, i)
            if m1 == 0:
                continue

            for j in range(n):
                if (i & (1 << j)) == 0:
                    dp[j] = 1
                else:
                    dp[j] = 0

            m2 = self.longestPalindromeSubseq(s, i, dp)
            res = max(res, m1 * m2)

        return res

    def palsize(self, s: str, mask: int) -> int:
        i, j = 0, len(s) - 1
        res = 0
        while i <= j:
            if (mask & (1 << i)) == 0:
                i += 1
            elif (mask & (1 << j)) == 0:
                j -= 1
            else:
                if s[i] != s[j]:
                    return 0
                res += 1 if i == j else 2
                i += 1
                j -= 1
        return res