leetcode

commit 91183f92ac13aa4ca9cc6d18629483aa9762b54e
parent fc94f09b9c8d3cd65899459e9b2e2e58ab3b3919
Author: Jack Sangdahl <jack@pngu.org>
Date:   Sun,  2 Nov 2025 21:29:06 -0700

1578. minimum time to make rope colourful

Diffstat:
M
min_time_make_rope_colourful.c
 | 
40
++++++++++++++--------------------------
M
min_time_make_rope_colourful.py
 | 
32
++++++++++++++++----------------

2 files changed, 30 insertions(+), 42 deletions(-)
diff --git a/min_time_make_rope_colourful.c b/min_time_make_rope_colourful.c
@@ -7,38 +7,26 @@
  * the rope to be colourful. she does not want two consecutive balloons to be
  * the of the same colour, so she asks bob for help. bob can remove some
  * balloons from the rope to make it colourful. you are given a 0-indexed
- * integer array 'needed_time' where 'needed_time[i]' is the time (in seconds)
+ * integer array 'neededTime' where 'neededTime[i]' is the time (in seconds)
  * that bob needs to remove the i'th balloon from the rope. return the minimum
  * time bob needs to make the rop colourful.
  */
 
-int calc_cost(int idx, int continue_len, int *needed_time) {
-  int max = needed_time[idx], sum = 0;
-  for (int i = idx; i < idx + continue_len; i++) {
-    sum += needed_time[i];
-    if (i + 1 < idx + continue_len)
-      if (needed_time[i + 1] > max)
-        max = needed_time[i + 1];
-  }
-  return sum - max;
-}
-
-int minCost(char *colours, int *needed_time, int needed_time_size) {
-  int continue_len = 1, idx = 0, min_cost = 0, cost = 0;
-  for (int i = 0; i < needed_time_size; i++) {
-    if (colours[i] == colours[i + 1]) {
-      continue_len++;
-      idx = i - continue_len - 2;
-    } else {
-      if (continue_len != 1) {
-        cost = calc_cost(idx, continue_len, needed_time);
-        min_cost += cost;
-        cost = 0;
-      }
-      continue_len = 1;
+int minCost(char *colors, int *neededTime, int neededTimeSize) {
+  int ans = 0, n = strlen(colors);
+  for (int i = 1; i < n; i++) {
+    int max = 0;
+    while (i < n && colors[i] == colors[i - 1]) {
+      ans += neededTime[i - 1];
+      max = fmax(max, neededTime[i - 1]);
+      ++i;
     }
+    ans += neededTime[i - 1];
+    max = fmax(max, neededTime[i - 1]);
+    if (max != 0)
+      ans -= max;
   }
-  return min_cost;
+  return ans;
 }
 
 int main() {
diff --git a/min_time_make_rope_colourful.py b/min_time_make_rope_colourful.py
@@ -19,23 +19,23 @@ class Solution(object):
         :type neededTime: List[int]
         :rtype: int
         """
-        cost = 0
-        i = 0
-        j = 0
-        while i < len(neededTime) and j < len(neededTime):
-            curr_cost = 0
-            curr_max = 0
-            while j < len(neededTime) and colors[i] == colors[j]:
-                curr_cost += neededTime[j]
-                curr_max = max(curr_max, neededTime[j])
-                j += 1
-            cost += curr_cost - curr_max
-            i = j
-        return cost
+        n, i, ans = len(colors), 1, 0
+        while i < n:
+            max_i = 0
+            while i < n and colors[i] == colors[i - 1]:
+                ans += neededTime[i - 1]
+                max_i = max(max_i, neededTime[i - 1])
+                i += 1
+            ans = neededTime[i - 1]
+            max_i = max(max_i, neededTime[i - 1])
+            if max_i != 0:
+                ans -= max_i
+            i += 1
+        return ans
 
 
 if __name__ == "__main__":
     obj = Solution()
-    print(obj.minCost("abaac", [1, 2, 3, 4, 5]))  # expect: 3
-    print(obj.minCost("abc", [1, 2, 3]))  # expect: 0
-    print(obj.minCost("aabaa", [1, 2, 3, 4, 1]))  # expect: 2
+    print(obj.minCost("abaac", [1, 2, 3, 4, 5]))
+    print(obj.minCost("abc", [1, 2, 3]))
+    print(obj.minCost("aabaa", [1, 2, 3, 4, 1]))