Hint Alice has n balloons arranged on a rope. You ...

Here are a few graded hints—stop whenever you’ve got it:

Hint 1:
Look at runs of consecutive balloons with the same color. Within any such run, after removals there must be exactly one balloon left.

Hint 2:
For a run of equal colors, to minimize time you should keep the balloon with the largest neededTime and remove all the others. So the cost for a run is sum(neededTime in the run) - max(neededTime in the run).

Hint 3 (one-pass trick):
You don’t need to pre-build runs. Walk left→right; whenever colors[i] == colors[i-1], add min(neededTime[i], neededTime[i-1]) to the answer and treat the remaining “kept” time as max(neededTime[i], neededTime[i-1]) for the next comparison (i.e., carry the bigger time forward). This collapses each run on the fly.

Tiny example:
colors = "aabaa", neededTime = [1,2,3,4,1]
Runs: "aa" (1,2) → keep 2 (pay 1); "b" → 0; "aa" (4,1) → keep 4 (pay 1).
Total = 1 + 0 + 1 = 2.

Here’s a clean O(n) one-pass solution. We keep the most expensive balloon in each same-color run and delete the rest.

cpp
#include <bits/stdc++.h>
using namespace std;

long long minCost(string colors, const vector<int>& neededTime) {
    const int n = (int)colors.size();
    if (n == 0) return 0;

    long long ans = 0;
    int keep = neededTime[0]; // max time kept in the current same-color run

    for (int i = 1; i < n; ++i) {
        if (colors[i] == colors[i - 1]) {
            // Remove the cheaper of the two; keep the higher cost for future comparisons
            ans += min(keep, neededTime[i]);
            keep = max(keep, neededTime[i]);
        } else {
            // New color run starts
            keep = neededTime[i];
        }
    }
    return ans;
}

// Example usage
int main() {
    string colors = "aabaa";
    vector<int> neededTime = {1, 2, 3, 4, 1};
    cout << minCost(colors, neededTime) << "\n"; // Output: 2
    return 0;
}

Why this works

• For any run of identical colors, you must leave exactly one balloon.
• Minimizing time = delete all but the one with the largest neededTime in that run.
• The loop merges runs on the fly by always adding the smaller of the current pair and carrying forward the larger as the “kept” one.

Complexity: O(n) time, O(1) extra space.