LeetCode Entry

1578. Minimum Time to Make Rope Colorful

27.12.2023 medium 2023 kotlin

Min sum of removed duplicates in array.

1578. Minimum Time to Make Rope Colorful medium blog post substack youtube image.png

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/remove 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 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
  }