Minimum Deletions to Make Character Frequencies Unique Solution
Minimum Deletions to Make Character Frequencies Unique solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Minimum Deletions to Make Character Frequencies Unique is a medium coding problem on strings, hash table and sorting, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Medium
- Topics: Strings, Hash Table, Sorting, Greedy
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A string is good if no two different characters occur the same number of times.
Given a string s, return the minimum number of characters you must delete to make it good.
Example 1
Input: s = "aab"
Output: 0
Explanation: a occurs twice and b once — already good.
Example 2
Input: s = "aaabbbcc"
Output: 2
Explanation: Deleting two c's gives frequencies 3, 3 — no; deleting one b and one c gives 3, 2, 1.
Example 3
Input: s = "ceabaacb"
Output: 2
Constraints
1 <= s.length <= 40s consists of lowercase English letters.
Hints for Minimum Deletions to Make Character Frequencies Unique
Hint 1
Only the 26 frequencies matter, not the characters themselves.
Hint 2
Process the frequencies and keep a set of the ones already taken.
Hint 3
While the current frequency is taken, delete one character — decrement it and count the deletion — until it is free or reaches zero.
How to solve Minimum Deletions to Make Character Frequencies Unique
Only the 26 frequencies matter. Process them keeping a set of used frequencies; while a frequency collides, decrement it (one deletion each) until it is free or zero.
Approach
- Count letters.
- For each non-zero count
f: whilef > 0andfis used,f -= 1and count a deletion; then markfused if positive.
Why it works
A collision must be resolved by lowering one of the two frequencies, and lowering to the next free value below is the cheapest fix; processing in descending order (or any order with the while loop) never forces extra deletions because a frequency dropped to zero removes the letter entirely, which is always allowed.
Complexity
- Time —
O(n + 26²) - Space —
O(26)
Pitfalls
- Dropping a frequency to 0 is fine — it just means deleting every copy of that letter.
Reference solution
Python
def minDeletions(s: str) -> int:
count = [0] * 26
for ch in s:
count[ord(ch) - 97] += 1
used = set()
deletions = 0
for f in count:
while f > 0 and f in used:
f -= 1
deletions += 1
if f > 0:
used.add(f)
return deletionsJava
public static int minDeletions(String s) {
int[] count = new int[26];
for (int i = 0; i < s.length(); i++) count[s.charAt(i) - 'a']++;
Set<Integer> used = new HashSet<>();
int deletions = 0;
for (int c = 0; c < 26; c++) {
int f = count[c];
while (f > 0 && used.contains(f)) {
f--;
deletions++;
}
if (f > 0) used.add(f);
}
return deletions;
}C++
int minDeletions(string s) {
vector<int> count(26, 0);
for (char ch : s) count[ch - 'a']++;
unordered_set<int> used;
int deletions = 0;
for (int c = 0; c < 26; c++) {
int f = count[c];
while (f > 0 && used.count(f) > 0) {
f--;
deletions++;
}
if (f > 0) used.insert(f);
}
return deletions;
}JavaScript
var minDeletions = function(s) {
const count = new Array(26).fill(0);
for (let i = 0; i < s.length; i++) count[s.charCodeAt(i) - 97]++;
const used = new Set();
let deletions = 0;
for (let c = 0; c < 26; c++) {
let f = count[c];
while (f > 0 && used.has(f)) {
f--;
deletions++;
}
if (f > 0) used.add(f);
}
return deletions;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets