leetcode

commit 15a1f85af72bc9d92154b9d2e5788b417cc7fe62
parent 5d15ab57b80ee97c427058cd8841847ea943dec1
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Tue, 19 Mar 2024 17:20:01 +0000

1 Random Problem

Diffstat:
A
Problems/2767.cpp
 | 
21
+++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 22 insertions(+), 0 deletions(-)
diff --git a/Problems/2767.cpp b/Problems/2767.cpp
@@ -0,0 +1,21 @@
+class Solution {
+    int rec(const char *s, const int n, int i) const {
+        if (i == n) return 0;
+        if (s[i] == '0') return -1;
+
+        int res = INT_MAX, crnt = 0;
+        for (; i < n; i++) {
+            crnt = (crnt << 1) | (s[i] & 1);
+            if (15625 % crnt == 0) {
+                const int next = rec(s, n, i + 1);
+                if (next == -1) continue;
+                res = min(res, 1 + next);
+            }
+        }
+
+        return res != INT_MAX ? res : -1;
+    }
+
+  public:
+    int minimumBeautifulSubstrings(const string &s) const { return rec(s.data(), size(s), 0); }
+};
diff --git a/README.md b/README.md
@@ -1144,6 +1144,7 @@ for solving problems.
 |  2740  |   Medium   | [Find the Value of the Partition](Problems/2740.cpp)                                               |
 |  2742  |    Hard    | [Painting the Walls](Problems/2742.cpp)                                                            |
 |  2745  |   Medium   | [Construct the Longest New String](Problems/2745.cpp)                                              |
+|  2767  |   Medium   | [Partition String Into Minimum Beautiful Substrings](Problems/2767.cpp)                            |
 |  2780  |   Medium   | [Minimum Index of a Valid Split](Problems/2780.cpp)                                                |
 |  2785  |   Medium   | [Sort Vowels in a String](Problems/2785.cpp)                                                       |
 |  2799  |   Medium   | [Count Complete Subarrays in an Array](Problems/2799.cpp)                                          |