From ea06e128606ea42e2b2c25d73e94e7d352f5e79d Mon Sep 17 00:00:00 2001 From: Jack Sangdahl Date: Thu, 17 Apr 2025 09:53:17 -0600 Subject: 2002. maximum product of the length of two palindromic subsequences --- max_product_len_palindrome_subseq.c | 46 ++++++++++++++++++++++++++++++++++++ max_product_len_palindrome_subseq.py | 46 ++++++++++++++++++++++++++++++++++++ 2 files changed, 92 insertions(+) create mode 100644 max_product_len_palindrome_subseq.c create mode 100644 max_product_len_palindrome_subseq.py diff --git a/max_product_len_palindrome_subseq.c b/max_product_len_palindrome_subseq.c new file mode 100644 index 0000000..b3e3a66 --- /dev/null +++ b/max_product_len_palindrome_subseq.c @@ -0,0 +1,46 @@ +// 2002. Maximum Product of the Length of Two Palindromic Subsequences +#include "leetcode.h" + +/* + * 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 + */ + +int maxProduct(char *s) { + int n = strlen(s), *bits = (int *)calloc(1 << n, sizeof(int)); + for (int i = 1; i < 1 << n; i++) + bits[i] = bits[i >> 1] + (i & 1); + for (int i = (1 << n) - 1; i >= 0; i--) { + int l = 0, r = n - 1; + while (l < r) { + while (l < n && !(i & (1 << l))) + l++; + while (r >= 0 && !(i & (1 << r))) + r--; + if (l < r && s[l] != s[r]) { + bits[i] = 0; + break; + } + l++, r--; + } + } + int ans = 1; + for (int i = (1 << n) - 1; i > 0; i--) + if (bits[i]) + for (int j = (i + 1) & ~i; j < 1 << n; j = ((j | i) + 1) & ~i) + if (bits[j]) + ans = fmax(ans, bits[i] * bits[j]); + return ans; +} + +int main() { + char *s1 = "leetcodecom", *s2 = "bb", *s3 = "accbcaxxcxx"; + printf("%d\n", maxProduct(s1)); // expect: 9 + printf("%d\n", maxProduct(s2)); // expect: 1 + printf("%d\n", maxProduct(s3)); // expect: 25 +} 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")) -- cgit v1.2.3