aboutsummaryrefslogtreecommitdiff
path: root/max_product_len_palindrome_subseq.c
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-04-17 09:53:17 -0600
committerJack Sangdahl <[email protected]>2025-04-17 09:53:17 -0600
commitea06e128606ea42e2b2c25d73e94e7d352f5e79d (patch)
tree10b6b2059731a55259cb7c54735e11a9cf0a224b /max_product_len_palindrome_subseq.c
parent614e2a72867982fe67dd0c6351ae647fbb1b7866 (diff)
downloadleetcode-ea06e128606ea42e2b2c25d73e94e7d352f5e79d.tar.gz
leetcode-ea06e128606ea42e2b2c25d73e94e7d352f5e79d.zip
2002. maximum product of the length of two palindromic subsequences
Diffstat (limited to 'max_product_len_palindrome_subseq.c')
-rw-r--r--max_product_len_palindrome_subseq.c46
1 files changed, 46 insertions, 0 deletions
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
+}