class Solution:
def maxProduct(self, s: str) -> int:
n=len(s)
total=[] #存放所有回文子序列
for i in range(1,1<<n): #用位运算列出所有子序列
temp=''
for j in range(n):
if (1<<j)&i:
temp+=s[j]
if temp==temp[::-1]: #判断是否为回文
total.append(i)
def count1(m:int): #统计二进制中1的个数
res=0
while m:
res+=(m&1)
m>>=1
return res
ret=0
for i in range(len(total)):
for j in range(i+1,len(total)):
if total[i]&total[j]==0: # total[i]&total[j]为0说明俩子序列不相交
ret=max(ret,count1(total[i])*count1(total[j]))
return ret #1的个数表示回文序列的长度，并计算俩长度的乘积
func maxProduct(s string) (ans int) {
var a, b []byte
var f func(int)
f = func(i int) {
if i == len(s) {
if len(a)*len(b) > ans && isPalindromic(a) && isPalindromic(b) {
ans = len(a) * len(b)
}
return
}
// 不选
f(i + 1)
// 放入 a
a = append(a, s[i])
f(i + 1)
a = a[:len(a)-1]
// 放入 b
b = append(b, s[i])
f(i + 1)
b = b[:len(b)-1]
}
f(0)
return
}
func isPalindromic(a []byte) bool {
for i, n := 0, len(a); i < n/2; i++ {
if a[i] != a[n-1-i] {
return false
}
}
return true
}
