aboutsummaryrefslogtreecommitdiff
path: root/max_product_len_palindrome_subseq.py
diff options
context:
space:
mode:
Diffstat (limited to 'max_product_len_palindrome_subseq.py')
-rw-r--r--max_product_len_palindrome_subseq.py46
1 files changed, 46 insertions, 0 deletions
diff --git a/max_product_len_palindrome_subseq.py b/max_product_len_palindrome_subseq.py
new file mode 100644
index 0000000..52ecafc
--- /dev/null
+++ b/max_product_len_palindrome_subseq.py
@@ -0,0 +1,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"))