leetcode

commit 06a16bbc1261b7587a5373b10c194649ab73d905
parent e042766995d0e1e9a550d9f0993af59d72b34be6
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Thu, 28 Dec 2023 16:11:07 +0000

Daily Problem

Diffstat:
A
Problems/1531.cpp
 | 
28
++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 29 insertions(+), 0 deletions(-)
diff --git a/Problems/1531.cpp b/Problems/1531.cpp
@@ -0,0 +1,28 @@
+class Solution {
+    static int dp[127][127];
+
+    static int digits(int x) {
+        if (x == 1) return 0;
+        if (x < 10) return 1;
+        if (x < 100) return 2;
+        return 3;
+    }
+
+  public:
+    Solution() { memset(dp, 0xFF, sizeof(dp)); }
+    int getLengthOfOptimalCompression(const string &s, int k, int crnt = 0) const {
+        const int n = s.size();
+        if (k < 0) return n;
+        if (crnt >= n || n - crnt <= k) return 0;
+        if (dp[crnt][k] != -1) return dp[crnt][k];
+        int res = n, cnt[27] = {0};
+        for (int j = crnt, maxi = 0; j < n; j++) {
+            maxi = max(maxi, ++cnt[s[j] & 0x1F]);
+            res = min(res,
+                      1 + digits(maxi) + getLengthOfOptimalCompression(s, k - (j - crnt + 1 - maxi), j + 1));
+        }
+        return dp[crnt][k] = res;
+    }
+};
+
+int Solution::dp[127][127];
diff --git a/README.md b/README.md
@@ -744,6 +744,7 @@ for solving problems.
 |  1527  |    Easy    | [Patients With a Condition](Problems/1527.cpp)                                                     |
 |  1529  |   Medium   | [Minimum Suffix Flips](Problems/1529.cpp)                                                          |
 |  1530  |   Medium   | [Number of Good Leaf Nodes Pairs](Problems/1530.cpp)                                               |
+|  1531  |    Hard    | [String Compression II](Problems/1531.cpp)                                                         |
 |  1535  |   Medium   | [Find the Winner of an Array Game](Problems/1535.cpp)                                              |
 |  1539  |    Easy    | [Kth Missing Positive Number](Problems/1539.cpp)                                                   |
 |  1544  |    Easy    | [Make The String Great](Problems/1544.cpp)                                                         |