The string colors gives the colors of balloons along a rope, in order. Removing balloon i takes neededTime[i] seconds. After a removal, the balloons on either side become neighbors. Return the minimum total removal time needed so that no two remaining neighboring balloons have the same color. You may leave an already valid rope unchanged.
Diagram circles show colors as letters; the numbers underneath show removal times.
Example 1:
Input: colors = "aabbc"
neededTime = [4,1,2,7,3]
Output: 3Explanation: Remove the second a for 1 second and the first b for 2 seconds. The remaining colors are abc, and the total time is 3 seconds. Choosing the cheaper removal within each repeated group is optimal.
Example 2:
Input: colors = "abc"
neededTime = [9,8,7]
Output: 0Explanation: Every neighboring pair already has different colors. No balloons need to be removed, so the answer is 0.
Example 3:
Input: colors = "aaaa"
neededTime = [3,8,5,2]
Output: 10Explanation: Only one a can remain. Keep the balloon that would cost 8 seconds to remove, and remove the others for 3 + 5 + 2 = 10 seconds.
Constraints:
1 <= colors.length == neededTime.length <= 100000colorscontains only lowercase English letters.1 <= neededTime[i] <= 10000