Problem 1578 (Dec 27)

(Last updated: )

Question statement:

Alice has $n$ balloons arranged on a rope. You are given a $0$-indexed string colors where $\texttt{colors[i]}$ is the color of the i-th balloon. Alice wants the rope to be colorful. She does not want two consecutive balloons to be of the same color, so she asks Bob for help. Bob can remove some balloons from the rope to make it colorful. You are given a $0$-indexed integer array neededTime where $\texttt{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 rope colorful.

For example: If $\texttt{colors = aabaccc}$ and $\texttt{neededTime = [2,3,1,2,4,2,1]}$, then the time required for Bob to make the string colorful is $5$ seconds, wherein Bob needs to remove the first ‘a’ and the last two ‘c’s, which takes $2+2+1=5$ seconds.

Solution:

The main idea:

  • Go through $\texttt{colors}$ and identify all ‘chains’ of the same letter.
  • Given a chain $C$ of length $d$ of a certain letter, we’ll choose to remove $d-1$ of them from that chain.
  • The choice that minimizes the time spent is the one where we leave behind the balloon that takes the most amount of time to remove.
  • Thus the time needed to remove the $d-1$ balloons is precisely
    $$\text{(total time to remove all balloons from $C$) – (max time to remove a balloon from $C$)}$$
  • Do this for every chain that appears in $\texttt{colors}$, and add up all the corresponding required times.

Identifying chains and corresponding times:

We use a sliding window (two pointer) trick for this. Suppose we have a window with a $\texttt{left}$ end initialized to $0$ and $\texttt{right}$ end initialized to $1$. In the example given, the initial setup would look like $\texttt{[aa]baccc}$. Now, we check if $\texttt{colors[left]}$ equals $\texttt{colors[right]}$, and if it is, we capture the corresponding time for $\texttt{colors[right]}$ into a different array $\texttt{times}$, that is initialized with $\texttt{neededTime[left]}$. In this case $\texttt{times} = [2,3]$ after the first check. Then we expand the window by adding $1$ to right, and see if this new window captures a chain. In this example, it doesn’t. So we are left with $\texttt{times} = [2,3]$. The optimal move is to remove the balloon that takes $2$ seconds, which is precisely $\texttt{sum(times)} - \texttt{max(times)}$. Finally, reset the window by setting $\texttt{left = right} (= 2)$ and $\texttt{right = right+1}$. Continue.

Note: If you don’t capture a non-trivial chain (if $\texttt{len(times)} = 1$), then let $\texttt{left +=1}$ and $\texttt{right+=1}$, initialize $\texttt{times}$ with $\texttt{neededTime[left]}$ and continue.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def minCost(self, colors: str, neededTime: List[int]) -> int:
    total_time = 0
    left = 0
    right = 1
    times = []
    while(right < len(colors)):
        times.append(neededTime[left])
        while(right < len(colors) and colors[left] == colors[right]):
            times.append(neededTime[right])
            right += 1    
        if(len(times) == 1):
            left += 1
            right +=1
            times = []
            continue
        req_time = sum(times) - max(times)
        total_time += req_time
        left = right
        right += 1
        times = []
    return total_time

Comments:

Time complexity: O(n).

At the time of submission, the above solution passes leetcode submission cases in 779ms, beats 98.6% of users. It uses 28.24MB of memory, beating 9.18% of users.