AlgoMaster Logo

Minimum Deletions to Make Character Frequencies Unique

mediumFrequencyUpdated September 21, 2026

Understanding the Problem

We need to make every character in the string have a unique frequency. Two characters can't share the same count. If 'a' appears 3 times and 'b' also appears 3 times, we have a conflict. We need to delete characters (reduce frequencies) until no two characters have the same non-zero frequency.

One detail drives the whole solution: a frequency of 0 doesn't count. If we delete all occurrences of a character, it no longer exists in the string. Multiple characters can have frequency 0 without conflict. So the question becomes: given a multiset of positive frequencies, what's the minimum total reduction needed so that every remaining positive value is distinct?

This is a greedy problem. When two characters share the same frequency, we reduce one of them to the next available lower frequency. Reducing by as little as possible at each step minimizes total deletions.

Key Constraints:

  • 1 <= s.length <= 10^5. A solution that enumerates all deletion combinations is exponential and infeasible at this size, so we need something close to linear.
  • s contains only lowercase English letters. There are at most 26 distinct characters. Frequency counting uses constant space, and any work proportional to the alphabet size is O(1).

Approach 1: Brute Force (Try All Frequency Assignments)

Intuition

We have a list of character frequencies and need to reduce some of them so that all remaining positive values are distinct. The most direct solution tries every possible combination of reductions and keeps the one with the lowest total cost.

For each frequency, we can reduce it to any value between 0 and its current value. We then check whether the resulting set of positive frequencies has any duplicates, and track the minimum deletions across all valid configurations. Backtracking with a used set lets us enumerate these target assignments while pruning branches that already cost more than the best answer found so far.

This is exponential in the number of distinct characters, but it makes the underlying problem precise: we are choosing a target frequency for each character that minimizes total reductions while keeping all positive targets unique.

Algorithm

  1. Count the frequency of each character in the string.
  2. Collect all non-zero frequencies into a list.
  3. For each non-zero frequency, try reducing it to every value from 0 to its current value.
  4. Use backtracking to enumerate all valid combinations where no two positive values match.
  5. Track the minimum total deletions across all valid combinations.

Visualization and Code

Loading animation...

The backtracking explores many more assignments than it needs to. Processing frequencies from largest to smallest collapses the choice at each step to a single option, which removes the search entirely.

Approach 2: Greedy with Sorting (Optimal)

Intuition

Sorting the frequencies in descending order removes the search. Process each frequency from largest to smallest while tracking the largest value still available, which starts one below the previous kept frequency. If the current frequency is already at or below that ceiling, keep it and lower the ceiling to match. If it is above the ceiling, reduce it down to the ceiling (or to 0 if the ceiling has fallen below 0) and charge the difference as deletions.

Greedy is safe here because deletions only move frequencies down, never up, and a larger frequency can always afford to occupy a higher slot than a smaller one. Taking the highest slot for each frequency, in descending order, never blocks a later frequency from a slot it could have used, since every later frequency is smaller and only needs a slot below the current one. Any optimal assignment can therefore be transformed into this greedy one without increasing the total reduction.

This works like assigning numbered slots from high to low. The first value keeps its slot. Each later value takes the highest open slot at or below its original count. If its original slot is taken, it slides down to the next open one.

Algorithm

  1. Count the frequency of each character.
  2. Collect the non-zero frequencies and sort them in descending order.
  3. Walk through the sorted frequencies. For each one:
    • If it's greater than or equal to the previous allowed value, reduce it to one less than the previous value.
    • If the target would go below 0, set it to 0 (delete all of that character).
    • Add the difference (original - target) to the deletion count.
  4. Return the total deletion count.

Visualization and Code

Loading animation...

The sorting approach tracks a maxAllowed ceiling. The next approach reaches the same answer without sorting, by resolving each conflict directly against a set of taken frequencies.

Approach 3: Greedy with HashSet

Intuition

A HashSet can track which frequencies are already taken without any sorting. For each character frequency, if the value is already in the set, decrement it by 1 until it reaches a value not in the set or drops to 0. The total number of decrements across all characters is the answer.

This is the same greedy decision as the sorting approach, resolved one conflict at a time instead of through a descending pass. Each conflicting frequency slides down to the first open slot below it, which is the smallest possible reduction for that character. Because every decrement lands the value one step closer to an unused frequency and stops at the first gap, no character ever gives up more than it must.

Algorithm

  1. Count the frequency of each character.
  2. Create an empty HashSet to track used frequencies.
  3. Initialize a deletion counter to 0.
  4. For each non-zero frequency:
    • While the frequency is greater than 0 and already exists in the set, decrement it by 1 and increment the deletion counter.
    • If the frequency is still greater than 0, add it to the set.
  5. Return the deletion count.

Visualization and Code

Loading animation...