# Minimum Deletions to Make Character Frequencies Unique

## Problem

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

Input: s = "aab"
Output: 0
Explanation: s is already good.
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".
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 \leq s.length \leq 10^5$
• $s$ contains only lowercase English letters

Submit your solution at here

## Solution

### Approach

We use greedy approach here:

• We memorize frequency of each character
• Go from high frequency to low, while keeping track of the last frequency
• We use the last valid frequency to calculate deletion needed

### Complexity

• Time complexity: $O(n)$
• Space complexity: $O(1)$

### Code

Rust

use std::cmp::max;
use std::cmp::min;
impl Solution {
pub fn min_deletions(s: String) -> i32 {
let s = s.as_bytes();
let n = 26;
let mut freq = vec![0;n];
for &c in s {
let i = c as usize - 'a' as usize;
freq[i] += 1;
}
freq.sort_by(|a,b|b.cmp(&a));
let mut ret = 0;
let mut top = i32::MAX;
for x in freq {
let target = max(0, top - 1);
ret += max(0, x - target);
top = min(x, target);
}
return ret;
}
}

Kotlin

class Solution {
fun minDeletions(s: String): Int {
val freq = IntArray(26) {0}
for(c in s) freq[c-'a']++
freq.sortDescending()
var cost = 0
var top = Int.MAX_VALUE
for(x in freq) {
val target = Math.max(0, top - 1)
cost += Math.max(0, x - target)
top = Math.min(x, target)
}
return cost
}
}

C++

class Solution {
public:
int minDeletions(string s) {
int n = 26;
vector<int> freq(n, 0);
for(auto c: s) freq[c-'a']++;
sort(freq.rbegin(), freq.rend());
int top = INT_MAX;
int ret = 0;
for(auto x: freq) {
int target = max(0, top -1);
ret += max(0, x - target);
top = min(x, target);
}
return ret;
}
};
Made with love using Svelte, Three.js