1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
# 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"))
|