Skip to main content
Talentd

Minimum Deletions to Make Character Frequencies Unique - Solution & Explanation

MediumHash TableStringGreedySorting13 min readAsked at: Amazon, Microsoft, American Express +4
Practice this problem

Problem Statement

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 <= 105
  • s contains only lowercase English letters.

Approach Overview

Problem Overview: Given a string s, delete the minimum number of characters so that no two characters share the same frequency. After deletions, each remaining character count must be unique.

Approach 1: Frequency Array + Set (Greedy) (Time: O(n + k log k), Space: O(k))

Count how many times each character appears using a frequency array or a hash table. Sort or iterate through the frequencies and keep a set of frequencies already used. If a frequency is already present in the set, repeatedly decrement it (simulate deleting characters) until the value becomes zero or unique. Each decrement represents one deletion. This works because the greedy rule is simple: always keep the highest possible frequency that has not been used yet. The approach is efficient since the alphabet size (k) is small compared to the string length.

The key insight: reducing a frequency by one is always the best local move when a conflict occurs. Larger frequencies should be preserved as much as possible while pushing duplicates downward until they reach an unused value.

Approach 2: Priority Queue for Frequency Management (Time: O(n + k log k), Space: O(k))

Insert all character frequencies into a max heap (priority queue). Continuously compare the largest frequency with the next largest. If both are equal, decrement the top value and push it back into the heap if it remains greater than zero. Each decrement corresponds to deleting a character from that group. The heap ensures you always resolve conflicts starting from the highest counts.

This approach explicitly models the frequency ordering using a heap instead of sorting. It’s a natural fit when working with dynamic frequency adjustments and demonstrates understanding of greedy conflict resolution combined with sorting-like ordering behavior.

Recommended for interviews: The Frequency Array + Set greedy approach is typically expected. It is shorter, easier to reason about, and uses constant-size alphabet assumptions effectively. The priority queue method is slightly heavier but still valid and demonstrates good command of heaps and frequency management.

Approach 1: Using Frequency Array and Set

This approach involves using a frequency array to count the number of times each character appears. We then use a set to track frequencies that we have already seen, and decrement frequencies until they are unique.

In this implementation, we use Python's Counter from the collections module to count character frequencies. We also maintain a set to keep track of unique frequencies we have seen. For each character frequency, if it's already in the set, we decrement the frequency until it's unique.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(N), where N is the length of the string. Space Complexity: O(1) because the number of unique characters is limited (26 lowercase English letters).

Try this approach in the editor →

Approach 2: Priority Queue for Frequency Management

This approach uses a priority queue (or max heap) to manage frequencies, adjusting each frequency to maintain uniqueness from the highest to the lowest.

In this C++ solution, we first compute frequency counts in a vector. We then use a priority queue to keep higher frequencies at the top. When consecutive top elements (frequencies) are the same, we decrement and push back to keep them unique, counting deletions.

Code

C++JavaScript

C++

JavaScript

Complexity

Time Complexity: O(N log N) due to priority queue operations. Space Complexity: O(1), constrained space regarding character set size.

Try this approach in the editor →

Approach 3: Array + Sorting

First, we use an array cnt of length 26 to count the occurrences of each letter in the string s.

Then, we sort the array cnt in descending order. We define a variable pre to record the current number of occurrences of the letter.

Next, we traverse each element v in the array cnt. If the current pre is 0, we directly add v to the answer. Otherwise, if v geq pre, we add v - pre + 1 to the answer and decrement pre by 1. Otherwise, we directly update pre to v. Then, we continue to the next element.

After traversing, we return the answer.

The time complexity is O(n + |\Sigma| times log |\Sigma|), and the space complexity is O(|\Sigma|). Here, n is the length of the string s, and |\Sigma| is the size of the alphabet. In this problem, |\Sigma| = 26.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Approach 4: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Using Frequency Array and Set

Time Complexity: O(N), where N is the length of the string. Space Complexity: O(1) because the number of unique characters is limited (26 lowercase English letters).

Priority Queue for Frequency Management

Time Complexity: O(N log N) due to priority queue operations. Space Complexity: O(1), constrained space regarding character set size.

Array + Sorting—
Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Frequency Array + Set (Greedy)O(n + k log k)O(k)Best general solution when alphabet size is small and you want simple greedy logic
Priority Queue (Max Heap)O(n + k log k)O(k)Useful when modeling conflicts dynamically with heaps or when practicing priority queue patterns

Video Solution

Minimum Deletions to Make Character Frequencies Unique - Leetcode 1647 - Python • NeetCodeIO • 9,099 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.
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.
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.
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.

Ready to solve this problem?

Practice Minimum Deletions to Make Character Frequencies Unique with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Deletions to Make Array Beautiful

Next

Minimum Deletions to Make String K-Special