Minimum Deletions to Make Character Frequencies Unique

LeetCode 1770 | Difficulty: Medium

Medium

Problem Description

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^5`

- `s` contains only lowercase English letters.

Topics: Hash Table, String, Greedy, Sorting

---

Approach

Hash Map

Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?

When to use

Need fast lookups, counting frequencies, finding complements/pairs.

Greedy

At each step, make the locally optimal choice. The challenge is proving the greedy choice leads to a global optimum. Look for: can I sort by some criterion? Does choosing the best option now ever hurt future choices?

When to use

Interval scheduling, activity selection, minimum coins (certain denominations), Huffman coding.

String Processing

Consider character frequency counts, two-pointer approaches, or building strings efficiently. For pattern matching, think about KMP or rolling hash. For palindromes, expand from center or use DP.

When to use

Anagram detection, palindrome checking, string transformation, pattern matching.

---

Solutions

Solution 1: C# (Best: 220 ms)

Metric	Value
Runtime	220 ms
Memory	40.3 MB
Date	2020-11-12

Solution

public class Solution {
    public int MinDeletions(string s) {
        Dictionary<char, int> d = new Dictionary<char, int>();
    foreach (var c in s)
    {
        if(d.ContainsKey(c))
        d[c]++;
        else d[c] = 1;
        
    }
    
    List<int> seen = new List<int>();
    int result = 0;
    foreach (var kv in d)
    {
        int freq = kv.Value;
        while(freq>0 && seen.Contains(freq))
        {
            freq--;
            result++;
        }
        seen.Add(freq);
    }
    
    return result;
    }
}

---

Complexity Analysis

Approach	Time	Space
Sort + Process	$O(n log n)$	$O(1) to O(n)$
Hash Map	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Hash map gives O(1) lookup — think about what to use as key vs value.
• LeetCode provides 3 hint(s) for this problem — try solving without them first.

💡 Hints

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.