Minimum Deletions to Make Character Frequencies Unique Python/Java solution

Python and Java implementations usually compute character counts, then use a set to track which frequencies are already used. When a duplicate frequency appears, decrement it while counting deletions until the value becomes unique. The same logic works across languages with O(n + k log k) time complexity.

What is the best approach for Minimum Deletions to Make Character Frequencies Unique?

The most common solution uses a greedy strategy with a frequency array and a hash set. Count each character, then ensure every frequency is unique by decrementing duplicates until an unused value is found. This approach runs in O(n + k log k) time where n is the string length and k is the alphabet size, with O(k) extra space.

Is Minimum Deletions to Make Character Frequencies Unique asked at Google/Amazon/Meta?

This problem matches common interview patterns used by large tech companies including Google, Amazon, and Meta. It tests greedy reasoning, frequency counting, and handling collisions using data structures like sets or heaps.

What data structure is used in Minimum Deletions to Make Character Frequencies Unique?

Typical solutions rely on a hash table or frequency array to count characters and a hash set to track used frequencies. Another variation uses a max heap (priority queue) to repeatedly resolve duplicate frequency values.

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

Most optimal implementations run in O(n + k log k) time. Counting characters takes O(n), and managing the frequencies with sorting, a set, or a heap costs O(k log k). Space complexity is typically O(k) to store frequency counts and used values.

Description Hints 3 Solution Video 9:41

1647. Minimum Deletions to Make Character Frequencies Unique

Q: Is Minimum Deletions to Make Character Frequencies Unique easy or hard?

The problem is rated Medium because the greedy insight is not immediately obvious. Once you recognize that duplicate frequencies must be reduced step by step until unique, the implementation becomes straightforward using a set or priority queue.

Q: How to solve Minimum Deletions to Make Character Frequencies Unique in O(n)?

Start by counting character frequencies in O(n). Track used frequencies in a hash set and greedily reduce duplicates until each frequency becomes unique or zero. Because the alphabet size is bounded (e.g., 26 lowercase letters), the additional operations remain small, giving near-linear performance in practice.

Medium61.3% acceptance7 companies

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.

The frequency of a character in a string is the number of times it appears in the string. For example, in the string "aab", the frequency of 'a' is 2, while the frequency of 'b' is 1.

Example 1:

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

Example 2:

Input: s = "aaabbbcc"
Output: 2
Explanation: You can delete two 'b's resulting in the good string "aaabcc".
Another way it to delete one 'b' and one 'c' resulting in the good string "aaabbc".

Example 3:

Input: s = "ceabaacb"
Output: 2
Explanation: You can delete both 'c's resulting in the good string "eabaab".
Note that we only care about characters that are still in the string at the end (i.e. frequency of 0 is ignored).

Constraints:

1 <= s.length <= 10⁵
s contains only lowercase English letters.

Asked at 7 companies

American Express Smartnews General Motors Intuit Microsoft

Google Amazon

Topics

Hints open one at a time

Hint 1

As we can only delete characters, if we have multiple characters having the same frequency, we must decrease all the frequencies of them, except one.

Hint 2

Sort the alphabet characters by their frequencies non-increasingly.

Hint 3

Iterate on the alphabet characters, keep decreasing the frequency of the current character until it reaches a value that has not appeared before.

9:41

Still stuck?Read 4 approaches, or watch a walkthrough.

Open solution