leetcode

commit 221c3920e85e34f3fddec4c2310318ee286f1751
parent 7ec62407f51f619688588761ec7ebb034051f842
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Tue,  9 Jan 2024 22:24:56 +0000

1 Random Problem

Diffstat:
A
Problems/2002.cpp
 | 
26
++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 27 insertions(+), 0 deletions(-)
diff --git a/Problems/2002.cpp b/Problems/2002.cpp
@@ -0,0 +1,26 @@
+class Solution {
+    static int len(const string &s) { return len(s, 0, size(s) - 1); }
+    static int len(const string &s, int i, int j) {
+        int cnt = 0, maxi = 0;
+        while (i < j) {
+            if (s[i] == s[j])
+                cnt += 2, i++, j--;
+            else
+                maxi = max(maxi, cnt + len(s, i + 1, j--));
+        }
+        return max(maxi, cnt + (i == j));
+    }
+
+  public:
+    int maxProduct(const string &s) const {
+        int res = 0;
+        for (int mask = 0; mask < 1 << size(s); mask++) {
+            string first, second;
+            for (int crnt = mask, idx = 0; crnt; crnt >>= 1, idx++) {
+                (crnt & 1 ? first : second) += s[idx];
+            }
+            res = max(res, len(first) * len(second));
+        }
+        return res;
+    }
+};
diff --git a/README.md b/README.md
@@ -891,6 +891,7 @@ for solving problems.
 |  1980  |   Medium   | [Find Unique Binary String](Problems/1980.cpp)                                                     |
 |  1991  |    Easy    | [Find the Middle Index in Array](Problems/1991.cpp)                                                |
 |  1992  |   Medium   | [Find All Groups of Farmland](Problems/1992.cpp)                                                   |
+|  2002  |   Medium   | [Maximum Product of the Length of Two Palindromic Subsequences](Problems/2002.cpp)                 |
 |  2009  |    Hard    | [Minimum Number of Operations to Make Array Continuous](Problems/2009.cpp)                         |
 |  2023  |   Medium   | [Number of Pairs of Strings With Concatenation Equal to Target](Problems/2023.cpp)                 |
 |  2024  |   Medium   | [Maximize the Confusion of an Exam](Problems/2024.cpp)                                             |