diff options
Diffstat (limited to 'max_product_len_palindrome_subseq.py')
-rw-r--r-- | max_product_len_palindrome_subseq.py | 46 |
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")) |