# 12.09.2023 [1647. Minimum Deletions to Make Character Frequencies Unique]
Minimum removes duplicate frequency chars from string
12.09.2023
1647. Minimum Deletions to Make Character Frequencies Unique medium
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/337
Problem TLDR
Minimum removes duplicate frequency chars from string
Intuition
// b b c e b a b
// 1 1 1 4
Characters doesn’t matter, only frequencies. Let’s sort them and scan one-by-one from biggest to small and descriase max value.
Approach
Let’s use Kotlin collections API:
groupBy - converts string into groups by characters
sortedDescending - sorts by descending
sumBy - iterates over all values and sums the lambda result
Complexity
Time complexity:
O(n)Space complexity:
O(n)
Code
fun minDeletions(s: String): Int {
var prev = Int.MAX_VALUE
return s.groupBy { it }.values
.map { it.size }
.sortedDescending()
.sumBy {
prev = maxOf(0, minOf(it, prev - 1))
maxOf(0, it - prev)
}
}