LeetCode Entry

1578. Minimum Time to Make Rope Colorful

03.11.2025 medium 2025 kotlin rust

Min weighted removals to dedup

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

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1162

Problem TLDR

Min weighted removals to dedup #medium #greedy

Intuition

Scan from left to right, keep only max from islands of duplicates.

Approach

• how many extra variables you need?
• add all time at each step, remove max at change
• or, add all sum(window(min))

Complexity

• Time complexity: \(O(n)\)

• Space complexity: \(O(1)\)

Code

// 23ms
    fun minCost(c: String, t: IntArray) =
        (1..<c.length).sumOf { i -> if (c[i] != c[i-1]) 0 else
            min(t[i], t[i-1]).also { t[i] = max(t[i], t[i-1]) }
        }

// 3ms
    pub fn min_cost(c: String, t: Vec<i32>) -> i32 {
        c.bytes().zip(t.iter()).chunk_by(|(a,_)| *a).into_iter()
        .map(|(_, c)| {
            let (s,m) = c.fold((0, 0), |(s,m), (_, &t)| (s+t,m.max(t))); s-m
        }).sum()
    }