두 Palindromic Subsequence 길이의 최대 곱

주어진 문자열 s 에서 길이의 곱이 최대화되도록 s 의 두 개의 분리된 회문 부분 시퀀스를 찾습니다. 두 하위 시퀀스는 둘 다 동일한 인덱스에서 문자를 선택하지 않으면 분리됩니다.

두 팰린드롬 하위 시퀀스 길이의 가능한 최대 곱을 반환합니다.

하위 시퀀스는 나머지 문자의 순서를 변경하지 않고 일부 문자를 삭제하거나 전혀 삭제하지 않음으로써 다른 문자열에서 파생될 수 있는 문자열입니다. 앞뒤로 읽는 문자열이 같으면 회문(palindromic) 문자열입니다.

예 1:



입력: s = "leetcodecom"
출력: 9
설명: 최적의 솔루션은 첫 번째 하위 시퀀스에 대해 "ete"를 선택하고 두 번째 하위 시퀀스에 대해 "cdc"를 선택하는 것입니다.
길이의 곱은 3 * 3 = 9입니다.

예 2:

입력: s = "bb"
출력: 1
설명: 최적의 솔루션은 첫 번째 하위 시퀀스에 대해 "b"(첫 번째 문자)를 선택하고 두 번째 하위 시퀀스에 대해 "b"(두 번째 문자)를 선택하는 것입니다.
길이의 곱은 1 * 1 = 1입니다.

예 3:

입력: s = "accbcaxxcxx"
출력: 25
설명: 최적의 솔루션은 첫 번째 하위 시퀀스에 대해 "accca"를 선택하고 두 번째 하위 시퀀스에 대해 "xxcxx"를 선택하는 것입니다.
길이의 곱은 5 * 5 = 25입니다.

제약:

2 <= s.length <= 12

s는 영문 소문자로만 구성되어 있습니다.

해결책:

class Solution:
    def maxPalindrome(self, s, i, j, cache):
        key = 1100 * i + j
        if key in cache:
            return cache[key]
        if i == j:
            cache[key] = 1
        elif s[i] == s[j] and i + 1 == j:
            cache[key] = 2
        elif s[i] == s[j]:
            cache[key] = self.maxPalindrome(s, i + 1, j - 1, cache) + 2
        else:
            cache[key] = max(self.maxPalindrome(s, i, j - 1, cache), self.maxPalindrome(s, i + 1, j, cache))
        return cache[key]

    def maxProduct(self, s: str) -> int:
        self.cache = {}
        maxP = float('-inf')
        n = len(s)
        for mask in range(1 << n):
            sub = ""
            rest = ""
            for j in range(n):
                if mask & (1 << j):
                    sub += s[j]
                else:
                    rest += s[j]
            if len(sub) > 0 and len(rest) > 0:
                maxP = max(maxP, self.maxPalindrome(sub, 0, len(sub) - 1, {}) * self.maxPalindrome(rest, 0, len(rest) - 1, {}))
        return maxP