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 +++++++++++++++++++++++++++++++++++++ 1 file changed, 46 insertions(+) create mode 100644 max_product_len_palindrome_subseq.c (limited to 'max_product_len_palindrome_subseq.c') 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 +} -- cgit v1.2.3