Greedy Algorithms8 sections · 316 units
Open in Course

Problem - Minimum Deletions to Make Character Frequencies Unique

No duplicate frequencies

Given a string, delete minimum characters so that no two different characters have the same frequency. For s="aab"s = "aab", frequencies are a:2a:2, b:1b:1. Already unique, answer is 00. For s="aaabbbcc"s = "aaabbbcc", frequencies are a:3a:3, b:3b:3, c:2c:2. Delete one aa or bb to make them different. Answer is 11. Constraint: you can only delete characters, not add them. Deleting reduces a character's frequency. The goal is to make all non-zero frequencies distinct.

If two characters have the same frequency, you must reduce one of them until it differs or reaches zero.