Minimum Deletions to Make Character Frequencies Unique
Description
A string s is good if there are no two different characters with the same frequency. Return the minimum number of character deletions to make s good.
Examples
s = "aab"0Already good: a=2, b=1.
abcabc3Initial frequencies: a=2, b=2, c=2. All characters have the same frequency (2), so the task requires make them unique. It is possible to keep one character at frequency 2, reduce another to frequency 1, and reduce the third to frequency 0. This requires deleting 1+2=3 characters total.
ceabaacb2Initial frequencies: a=3, b=2, c=2, e=1. Characters b and c both have frequency 2, which violates the uniqueness requirement. It is possible to keep b at frequency 2 and reduce c to frequency 1, but frequency 1 is already taken by e. So reducing c to frequency 0 by deleting 2 characters.
Constraints
- •
1 ≤ s.length ≤ 10^5
Ready to solve this problem?
Practice solo and sharpen your skills for technical interviews.