1647 - Minimum Deletions to Make Character Frequencies Unique

Difficulty: Medium | Pattern: Greedy / Sorting | Company tags: Google, Amazon, DoorDash

Problem Statement

A string s is called good if there are no two different characters with the same frequency.

Given a string s, return the minimum number of characters you need to delete to make it good.

Example 1:

Input: s = "aab"
Output: 0  (frequencies: a=2, b=1 — already unique)

Example 2:

Input: s = "aaabbbcc"
Output: 2  (delete one 'b' and one 'c': frequencies a=3, b=2, c=1)

Example 3:

Input: s = "ceabaacb"
Output: 2

Algorithm Flow

Approach: Sort Frequencies + Greedy — O(n)

Key insight: Sort frequencies in descending order. For each frequency, if it equals the previous allowed frequency, reduce it by 1 (delete one character). Track the "last allowed" frequency to ensure uniqueness.

from collections import Counter

def minDeletions(s: str) -> int:
    freq = sorted(Counter(s).values(), reverse=True)
    deletions = 0
    max_allowed = freq[0]  # start with the highest frequency
    
    for f in freq:
        # Ensure this frequency doesn't exceed max_allowed
        actual = min(f, max_allowed)
        deletions += f - actual
        max_allowed = max(0, actual - 1)  # next must be at least 1 less
    
    return deletions

Approach 2: Set of Used Frequencies

from collections import Counter

def minDeletions(s: str) -> int:
    freq = Counter(s)
    used = set()
    deletions = 0
    
    for f in sorted(freq.values(), reverse=True):
        while f > 0 and f in used:
            f -= 1
            deletions += 1
        if f > 0:
            used.add(f)
    
    return deletions

Dry Run

s = "aaabbbcc" → freq: {a:3, b:3, c:2} → sorted: [3, 3, 2]

freq	max_allowed	actual	deletions
3	3	min(3,3)=3	0
3	2	min(3,2)=2	3-2=1
2	1	min(2,1)=1	2-1=1

Total: 2 ✓

Edge Cases

• All characters same → frequencies = [n] → 0 deletions (only one char, already unique)
• All unique characters → frequencies all 1 → delete all but one of each duplicate frequency
• Empty string → 0

Complexity

• Time: O(n log n) — O(n) to count, O(k log k) to sort frequencies (k = 26 max)
• Space: O(k) where k = alphabet size

Key Terms

Term	Definition
Frequency map	A count of how many times each character appears, typically built with Counter.
Greedy decrement	Repeatedly reducing a value by 1 until it satisfies a constraint (here, uniqueness) — locally optimal and never revisited.
Used-frequency set	A set tracking which frequency values are already "claimed" so later frequencies must avoid collisions.
Descending processing order	Handling the largest frequencies first so each conflict is resolved with the fewest possible deletions.

FAQ

Q: Why process frequencies in descending order? A: Processing largest-first ensures each value only needs to drop to the next free slot below it, minimizing wasted deletions compared to resolving smaller frequencies first.

Q: Can a frequency ever need to become 0? A: Yes — if many characters share overlapping frequency ranges, one frequency may be decremented all the way to 0, meaning that character is effectively deleted entirely.

Q: Why does max_allowed decrease by 1 after each frequency, not just track "already used" values? A: Approach 1 is a shortcut equivalent to Approach 2's set-based collision check — since frequencies are processed in sorted order, capping each one at previous - 1 produces the same result as skipping already-used values, but without the inner while loop.

Q: What if the string has more than 26 distinct characters (e.g., Unicode)? A: The algorithm is unaffected — it just uses Counter over any character set; the frequency-array optimization (fixed 26 slots) would need to become an unbounded dict, slightly changing space complexity from O(1) to O(unique chars).

Q: How is this different from a problem asking to make an array's elements unique with minimum removals? A: It's structurally identical — "make frequencies unique" is the same greedy-decrement-until-free-slot pattern used in problems like minimum decrements to make array elements distinct.

Quick Revision

• Pattern: greedy sorting — resolve conflicts starting from the largest values first.
• Count character frequencies, then sort them in descending order.
• Track the highest frequency still "available"; cap each subsequent frequency below it.
• Every unit reduction below the original frequency counts as one deletion.
• Equivalent formulation: use a set of claimed frequencies and decrement until a free value (or 0) is found.
• Frequency 0 means all copies of a character are deleted, which is allowed.
• Time complexity: O(n) to count + O(k log k) to sort (k ≤ 26 for lowercase letters); space O(k).
• Edge cases: single repeated character, all-unique characters, empty string.

Related Problems

• 242 - Valid Anagram — shares the frequency-counting foundation via Counter.
• 409 - Longest Palindrome — another greedy problem built directly on character frequency analysis.
• Pattern match: any "resolve duplicate values with minimum changes" problem (e.g., minimum decrements to make array unique) uses the same sort-and-greedily-shrink technique.