diff options
author | Jack Sangdahl <[email protected]> | 2025-04-17 09:53:17 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-04-17 09:53:17 -0600 |
commit | ea06e128606ea42e2b2c25d73e94e7d352f5e79d (patch) | |
tree | 10b6b2059731a55259cb7c54735e11a9cf0a224b | |
parent | 614e2a72867982fe67dd0c6351ae647fbb1b7866 (diff) | |
download | leetcode-ea06e128606ea42e2b2c25d73e94e7d352f5e79d.tar.gz leetcode-ea06e128606ea42e2b2c25d73e94e7d352f5e79d.zip |
2002. maximum product of the length of two palindromic subsequences
-rw-r--r-- | max_product_len_palindrome_subseq.c | 46 | ||||
-rw-r--r-- | max_product_len_palindrome_subseq.py | 46 |
2 files changed, 92 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 +} 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")) |