LeetCode Entry

1647. Minimum Deletions to Make Character Frequencies Unique

12.09.2023 medium 2023 kotlin

Minimum removes duplicate frequency chars from string

1647. Minimum Deletions to Make Character Frequencies Unique medium blog post substack image.png

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)
        }
    }