What is the time complexity of LeetCode 1647. Minimum Deletions to Make Character Frequencies Unique?

The Python solution on this page runs in O(n + |\Sigma| \times \log |\Sigma|).

What is the space complexity of LeetCode 1647. Minimum Deletions to Make Character Frequencies Unique?

The Python solution on this page uses O(|\Sigma|) auxiliary space.

Minimum Deletions to Make Character Frequencies Unique — LeetCode 1647 Python Solution

MediumGreedyHash TableStringSorting

Problem: #1647
Pattern: Greedy
Reading time: 2 min
Source: leetcode.com

The problem

A string s is called good if there are no two different characters in s that have the same frequency. Given a string s, return the minimum number of characters you need to delete to make s good.

Example

Input: s = "aab"
Output: 0
Explanation: s is already good.

Python solution

Python

class Solution:
    def minDeletions(self, s: str) -> int:
        cnt = Counter(s)
        ans, pre = 0, inf
        for v in sorted(cnt.values(), reverse=True):
            if pre == 0:
                ans += v
            elif v >= pre:
                ans += v - pre + 1
                pre -= 1
            else:
                pre = v
        return ans

Complexity

Measure	Complexity
Time	O(n + \|\Sigma\| \times \log \|\Sigma\|)
Space	O(\|\Sigma\|) auxiliary

Pattern: Greedy

Take the locally best option every time — when you can prove that never costs you later. LeetCode 1647. Minimum Deletions to Make Character Frequencies Unique is filed here because LeetCode tags it Greedy, which is the vocabulary this hub collects.

The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1647. Minimum Deletions to Make Character Frequencies Unique?: LeetCode 1647. Minimum Deletions to Make Character Frequencies Unique is rated Medium on LeetCode.
What is the time complexity of LeetCode 1647. Minimum Deletions to Make Character Frequencies Unique?: The Python solution on this page runs in O(n + |\Sigma| \times \log |\Sigma|).
What is the space complexity of LeetCode 1647. Minimum Deletions to Make Character Frequencies Unique?: The Python solution on this page uses O(|\Sigma|) auxiliary space.
What topics does LeetCode 1647. Minimum Deletions to Make Character Frequencies Unique cover?: LeetCode 1647. Minimum Deletions to Make Character Frequencies Unique is tagged Greedy, Hash Table, String and Sorting on LeetCode.