Minimum Deletions to Make Character Frequencies Unique

Medium
346.

Minimum Deletions to Make Character Frequencies Unique

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.

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 <= 40
  • s consists of lowercase English letters.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var minDeletions = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 40
  • s consists of lowercase English letters.

Hints for Minimum Deletions to Make Character Frequencies Unique

  1. Hint 1

    Only the 26 frequencies matter, not the characters themselves.

  2. Hint 2

    Process the frequencies and keep a set of the ones already taken.

  3. 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

  1. Count letters.
  2. For each non-zero count f: while f > 0 and f is used, f -= 1 and count a deletion; then mark f used 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 deletions

Java

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