Minimum Time to Make Rope Colorful

Medium
361.

Minimum Time to Make Rope Colorful

Minimum Time to Make Rope Colorful is a medium coding problem on arrays, strings and dynamic programming, asked in Amazon and Adobe interviews.

Alice has n balloons on a rope; colors[i] is the colour of the i-th balloon. The rope is colorful if no two consecutive balloons share a colour.

Bob can remove the i-th balloon at a cost of neededTime[i] seconds. Return the minimum total time needed to make the rope colorful.

Example 1

Input
colors = "abaac", neededTime = [1,2,3,4,5]
Output
3
Explanation
Remove the cheaper of the two consecutive a's.

Example 2

Input
colors = "abc", neededTime = [1,2,3]
Output
0

Example 3

Input
colors = "aabaa", neededTime = [1,2,3,4,1]
Output
2

Constraints

  • 1 <= colors.length <= 40
  • neededTime.length == colors.length
  • 1 <= neededTime[i] <= 10000
  • colors consists of lowercase English letters.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} colors
 * @param {number[]} neededTime
 * @return {number}
 */
var minCost = function(colors, neededTime) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Time to Make Rope Colorful — Problem & Solution

Minimum Time to Make Rope Colorful solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Minimum Time to Make Rope Colorful is a medium coding problem on arrays, strings and dynamic programming, asked in Amazon and Adobe interviews.

Problem statement

Alice has n balloons on a rope; colors[i] is the colour of the i-th balloon. The rope is colorful if no two consecutive balloons share a colour.

Bob can remove the i-th balloon at a cost of neededTime[i] seconds. Return the minimum total time needed to make the rope colorful.

Example 1

Input: colors = "abaac", neededTime = [1,2,3,4,5]
Output: 3
Explanation: Remove the cheaper of the two consecutive a's.

Example 2

Input: colors = "abc", neededTime = [1,2,3]
Output: 0

Example 3

Input: colors = "aabaa", neededTime = [1,2,3,4,1]
Output: 2

Constraints

  • 1 <= colors.length <= 40
  • neededTime.length == colors.length
  • 1 <= neededTime[i] <= 10000
  • colors consists of lowercase English letters.

Hints for Minimum Time to Make Rope Colorful

  1. Hint 1

    Balloons only conflict inside a run of one colour, and each run must be reduced to a single balloon.

  2. Hint 2

    Within a run, keep the most expensive balloon and remove the rest.

  3. Hint 3

    So each run contributes sum(run) - max(run).

How to solve Minimum Time to Make Rope Colorful

Balloons only conflict within a run of one colour, and each run must shrink to a single balloon — keep the most expensive one.

Approach

  1. Scan runs of equal colour.
  2. For each run add sum(times) - max(times).

Why it works

Runs are independent, and within a run removing all but the costliest balloon is the cheapest way to leave exactly one.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • The equivalent single-pass form keeps a running max per run and adds the smaller of each adjacent equal pair.

Reference solution

Python

def minCost(colors: str, neededTime) -> int:
    total = 0
    i = 0
    while i < len(colors):
        j = i
        run_sum = 0
        run_max = 0
        while j < len(colors) and colors[j] == colors[i]:
            run_sum += neededTime[j]
            run_max = max(run_max, neededTime[j])
            j += 1
        total += run_sum - run_max
        i = j
    return total

Java

public static int minCost(String colors, int[] neededTime) {
    int total = 0, i = 0;
    while (i < colors.length()) {
        int j = i, sum = 0, maxT = 0;
        while (j < colors.length() && colors.charAt(j) == colors.charAt(i)) {
            sum += neededTime[j];
            maxT = Math.max(maxT, neededTime[j]);
            j++;
        }
        total += sum - maxT;
        i = j;
    }
    return total;
}

C++

int minCost(string colors, vector<int>& neededTime) {
    int total = 0, i = 0;
    int n = (int) colors.size();
    while (i < n) {
        int j = i, sum = 0, maxT = 0;
        while (j < n && colors[j] == colors[i]) {
            sum += neededTime[j];
            maxT = max(maxT, neededTime[j]);
            j++;
        }
        total += sum - maxT;
        i = j;
    }
    return total;
}

JavaScript

var minCost = function(colors, neededTime) {
    let total = 0;
    let i = 0;
    while (i < colors.length) {
        let j = i, sum = 0, maxT = 0;
        while (j < colors.length && colors[j] === colors[i]) {
            sum += neededTime[j];
            if (neededTime[j] > maxT) maxT = neededTime[j];
            j++;
        }
        total += sum - maxT;
        i = j;
    }
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings