Skip to content

1578. Minimum Time to Make Rope Colorful 👍

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
 public:
  int minCost(string colors, vector<int>& neededTime) {
    int ans = 0;
    int maxNeededTime = neededTime[0];

    for (int i = 1; i < colors.length(); ++i)
      if (colors[i] == colors[i - 1]) {
        ans += min(maxNeededTime, neededTime[i]);
        // For each continuous group, Bob needs to remove every balloon except
        // the one with the maximum `neededTime`. So, he should hold the balloon
        // with the highest `neededTime` in his hand.
        maxNeededTime = max(maxNeededTime, neededTime[i]);
      } else {
        // If the current balloon is different from the previous one, discard
        // the balloon from the previous group and hold the new one in hand.
        maxNeededTime = neededTime[i];
      }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
  public int minCost(String colors, int[] neededTime) {
    int ans = 0;
    int maxNeededTime = neededTime[0];

    for (int i = 1; i < colors.length(); ++i)
      if (colors.charAt(i) == colors.charAt(i - 1)) {
        ans += Math.min(maxNeededTime, neededTime[i]);
        // For each continuous group, Bob needs to remove every balloon except the one with the max
        // `neededTime`. So, he should hold the balloon with the highest `neededTime` in his hand.
        maxNeededTime = Math.max(maxNeededTime, neededTime[i]);
      } else {
        // If the current balloon is different from the previous one, discard the balloon from the
        // previous group and hold the new one in hand.
        maxNeededTime = neededTime[i];
      }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
  def minCost(self, colors: str, neededTime: list[int]) -> int:
    ans = 0
    maxNeededTime = neededTime[0]

    for i in range(1, len(colors)):
      if colors[i] == colors[i - 1]:
        ans += min(maxNeededTime, neededTime[i])
        # For each continuous group, Bob needs to remove every balloon except
        # the one with the maximum `neededTime`. So, he should hold the balloon
        # with the highest `neededTime` in his hand.
        maxNeededTime = max(maxNeededTime, neededTime[i])
      else:
        # If the current balloon is different from the previous one, discard
        # the balloon from the previous group and hold the new one in hand.
        maxNeededTime = neededTime[i]

    return ans