27.12.2023
1578. Minimum Time to Make Rope Colorful medium blog post youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/452
Problem TLDR
Min sum of removed duplicates in array.
Intuition
The brute-force approach is to just consider keeping/removing every item, that can be cached in [size, 26] array.
However, there is a more optimal greedy solution: scan symbols one by one, and from each duplicate island remove the maximum of it.
Approach
Start from writing a more verbose solution, keeping separate variables for currentSum
, totalSum
, and two separate conditions: if we meet a duplicate or not. Then optimize it out.
Complexity
Time complexity: $$O(n)$$
Space complexity: $$O(1)$$
Code
fun minCost(colors: String, neededTime: IntArray): Int {
var sum = 0
var max = 0
var prev = '.'
for ((i, c) in colors.withIndex()) {
sum += neededTime[i]
if (prev != c) sum -= max.also { max = 0 }
max = max(max, neededTime[i])
prev = c
}
return sum - max
}