1647. Minimum Deletions to Make Character Frequencies Unique - Explanation

1. Hash Set

class Solution:
    def minDeletions(self, s: str) -> int:
        count = [0] * 26
        for c in s:
            count[ord(c) - ord('a')] += 1

        used_freq = set()
        res = 0
        for freq in count:
            while freq > 0 and freq in used_freq:
                freq -= 1
                res += 1
            used_freq.add(freq)

        return res

Time & Space Complexity

Time complexity: $O(n + m ^ 2)$
Space complexity: $O(m)$

Where $n$ is the length of the string $s$ and $m$ is the total number of unique frequncies possible.

2. Max-Heap

class Solution:
    def minDeletions(self, s: str) -> int:
        freq = Counter(s)
        maxHeap = [-f for f in freq.values()]
        heapq.heapify(maxHeap)

        res = 0
        while len(maxHeap) > 1:
            top = -heapq.heappop(maxHeap)
            if top == -maxHeap[0]:
                if top - 1 > 0:
                    heapq.heappush(maxHeap, -(top - 1))
                res += 1

        return res

Time & Space Complexity

Time complexity: $O(n + m ^ 2 \log m)$
Space complexity: $O(m)$

Where $n$ is the length of the string $s$ and $m$ is the total number of unique frequncies possible.

3. Sorting

class Solution:
    def minDeletions(self, s: str) -> int:
        count = [0] * 26
        for c in s:
            count[ord(c) - ord('a')] += 1

        count.sort(reverse=True)
        res = 0
        maxAllowedFreq = count[0]

        for freq in count:
            if freq > maxAllowedFreq:
                res += freq - maxAllowedFreq
                freq = maxAllowedFreq
            maxAllowedFreq = max(0, freq - 1)

        return res

Time & Space Complexity

Time complexity: $O(n + m \log m)$
Space complexity: $O(m)$

Where $n$ is the length of the string $s$ and $m$ is the total number of unique frequncies possible.