The question is obviously a dynamic programming question. By defining an array of minimum time needed to make the ballon sequence end with a specific colour (i.e., the array index). The algorithm is straightforward by the data structure definition.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function minCost(colors: string, neededTime: number[]): number {
const cost = Array(27).fill(100000000)
cost[0] = 0
for ( let i=0;i<colors.length;++i ) {
let c = colors.charCodeAt(i) - 96
let min = 100000000
for ( let j=0;j<27;++j ) {
if ( c !== j ) {
min = Math.min(min, cost[j])
cost[j] += neededTime[i]
}
}
cost[c] = Math.min(min, cost[c] + neededTime[i])
}
return cost.reduce((acc, cur) => Math.min(acc, cur), cost[0])
};