leetcode

commit 3e6d91298e2a97ca8c2b7c5d61741592a353ab2a
parent 15e8ea0ae319cb32dd524d8fc5835600d58bcae6
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Wed, 14 Feb 2024 20:11:27 +0000

1 Random Problem

Diffstat:
A
Problems/2712.cpp
 | 
36
++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 37 insertions(+), 0 deletions(-)
diff --git a/Problems/2712.cpp b/Problems/2712.cpp
@@ -0,0 +1,36 @@
+class Solution {
+  public:
+    long long minimumCost(const string &s) const {
+        static long long dp[100001];
+
+        const int n = size(s);
+        if (n == 1) return 0;
+
+        dp[0] = 0;
+        for (int i = 1; i < n; i++) {
+            dp[i] = s[i] == s[i - 1] ? dp[i - 1] : dp[i - 1] + i;
+        }
+
+        long long res = LLONG_MAX, acc = 0;
+        for (int i = n - 2; i >= 0; i--) {
+            if (s[i] != s[i + 1]) acc += n - i - 1;
+            res = min(res, dp[i] + acc);
+        }
+
+        return res;
+    }
+};
+
+// O(1) space
+class Solution {
+  public:
+    long long minimumCost(const string &s) const {
+        long long res = 0;
+
+        for (int i = 1, n = size(s); i < n; i++) {
+            if (s[i] != s[i - 1]) res += min(i, n - i);
+        }
+
+        return res;
+    }
+};
diff --git a/README.md b/README.md
@@ -1113,6 +1113,7 @@ for solving problems.
 |  2706  |    Easy    | [Buy Two Chocolates](Problems/2706.cpp)                                                            |
 |  2707  |   Medium   | [Extra Characters in a String](Problems/2707.cpp)                                                  |
 |  2711  |   Medium   | [Difference of Number of Distinct Values on Diagonals](Problems/2711.cpp)                          |
+|  2712  |   Medium   | [Minimum Cost to Make All Characters Equal](Problems/2712.cpp)                                     |
 |  2740  |   Medium   | [Find the Value of the Partition](Problems/2740.cpp)                                               |
 |  2742  |    Hard    | [Painting the Walls](Problems/2742.cpp)                                                            |
 |  2780  |   Medium   | [Minimum Index of a Valid Split](Problems/2780.cpp)                                                |