Sponsored
Sponsored
This is a greedy technique using two pointers. Iterate over the string of balloon colors. For each sequence of consecutive balloons of the same color, use one pointer to find the maximum time required to remove a balloon (among those consecutive balloons). Accumulate the total removal time by subtracting this maximum time from the sum of all removal times for the sequence.
Time Complexity: O(n), where n is the number of balloons. We iterate through the array once.
Space Complexity: O(1), no additional space is used other than a few variables.
1#include <stdio.h>
2#include <string.h>
3
4int minTime(char *colors, int *neededTime, int n) {
5 int totalCost = 0;
6 for (int i = 1; i < n; i++) {
7 if (colors[i] == colors[i - 1]) {
8 totalCost += neededTime[i] < neededTime[i-1] ? neededTime[i] : neededTime[i-1];
9 if (neededTime[i] < neededTime[i-1])
10 neededTime[i] = neededTime[i-1];
11 }
12 }
13 return totalCost;
14}
15
16int main() {
17 char colors[] = "aabaa";
18 int neededTime[] = {1, 2, 3, 4, 1};
19 int n = strlen(colors);
20 printf("%d\n", minTime(colors, neededTime, n));
21 return 0;
22}This approach uses dynamic programming (DP) with state compression to minimize the time required to make all the balloons non-consecutive in terms of color. The solution leverages optimization by compressing the state to monitor the necessary reduction within nested loops over sequences of consecutive duplicates.
Time Complexity: O(n), for looping through the list.
Space Complexity: O(1), only using a couple of elements for the DP state transitions.
1
This C solution utilizes a dynamic programming array to store minimum times dynamically adjusted as pairs of consecutive balloons come into play. It keeps track of multiple states based on whether the current or previous balloons of the same color should be retained.