leetcode: 1647. Minimum Deletions to Make Character Frequencies Unique

problem

• https://leetcode.com/problems/minimum-deletions-to-make-character-frequencies-unique/

sort

class Solution {
    fun minDeletions(s: String): Int {
        val freqs = Array<Int>(26) { 0 }
        s.forEach { c ->
            freqs[c.toInt() - 'a'.toInt()] += 1
        }
        freqs.sortBy { -it } // decreasing
        var prev = freqs[0]
        var answer = 0    

        for (i in 1 until 26) {
            if (freqs[i] == 0) break // following freq is 0 too.
            if (freqs[i] < prev) {
                prev = freqs[i]
                continue
            }
            
            // freqs[i] >= prev
            if (prev == 0) { // current freq must be 0
                answer += freqs[i] 
                prev = 0
            } else { // current freq must be (prev - 1)
                answer += (freqs[i] - prev + 1)    
                prev--
            }
        }
        return answer
    }
}

set

class Solution {
    fun minDeletions(s: String): Int {
        val freqs = Array<Int>(26) { 0 }
        s.forEach { c ->
            freqs[c - 'a'] += 1
        }
        
        val set = mutableSetOf<Int>()
        var answer = 0   
        freqs.forEach { freq ->
            var temp = freq
            while (temp > 0 && !set.add(temp)) {
                temp--
                answer++
            }
        }
        return answer
    }
}