Minimum Deletions to Make Character Frequencies Unique

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.

Input & Output

Example 1 — Basic Case

$ Input: s = "aab"

› Output: 0

💡 Note: Character frequencies: a=2, b=1. All frequencies are unique, so no deletions needed.

Example 2 — Need Deletions

$ Input: s = "aaabbbcc"

› Output: 2

💡 Note: Character frequencies: a=3, b=3, c=2. We have duplicate frequency 3. Reduce one character's frequency: 3→1, requiring 2 deletions.

Example 3 — Complex Case

$ Input: s = "ceabaacb"

› Output: 2

💡 Note: Character frequencies: a=3, b=2, c=2, e=1. Two characters have frequency 2. Reduce one to frequency 1, but that conflicts with e=1, so reduce to 0. Total: 2 deletions.

Constraints

1 ≤ s.length ≤ 10⁵
s consists of lowercase English letters only

Visualization

Tap to expand

Understanding the Visualization

Input

String with characters that may have duplicate frequencies

Process

Count frequencies and resolve conflicts optimally

Output

Minimum number of deletions needed

Key Takeaway

🎯 Key Insight: Process characters by frequency in descending order to minimize total deletions

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Facebook 6

The key insight is to use a greedy approach: count character frequencies, sort them in descending order, then assign the highest possible unique frequency to each character. This minimizes deletions by preserving as many high-frequency characters as possible. Best approach is Greedy with Sorting. Time: O(n + k log k), Space: O(k) where k ≤ 26.

Common Approaches

Approach	Time	Space	Notes
✓ Greedy with Sorting	O(n + k log k)	O(k)	Sort frequencies in descending order and greedily assign unique values
Brute Force with Set Checking	O(n²)	O(1)	Count frequencies, then repeatedly find and resolve conflicts

Greedy with Sorting — Algorithm Steps

Count frequency of each character
Sort frequencies in descending order
For each frequency, assign the highest available unique value
Count total deletions needed

Visualization

Tap to expand

Step-by-Step Walkthrough

Count & Sort

Get frequencies and sort in descending order

Greedy Assignment

Assign highest possible unique frequency to each character

Calculate Deletions

Sum up all the characters that need to be deleted

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void* a, const void* b) {
    return (*(int*)b - *(int*)a); // Descending order
}

int solution(char* s) {
    // Count frequencies (assuming lowercase letters)
    int freq[26] = {0};
    int len = strlen(s);
    
    for (int i = 0; i < len; i++) {
        freq[s[i] - 'a']++;
    }
    
    // Collect non-zero frequencies
    int frequencies[26];
    int count = 0;
    for (int i = 0; i < 26; i++) {
        if (freq[i] > 0) {
            frequencies[count++] = freq[i];
        }
    }
    
    // Sort frequencies in descending order
    qsort(frequencies, count, sizeof(int), compare);
    
    int deletions = 0;
    int nextAvailable = count > 0 ? frequencies[0] : 0;
    
    for (int i = 0; i < count; i++) {
        int currentFreq = frequencies[i];
        // Assign the minimum of current frequency and next available
        int assigned = currentFreq < nextAvailable ? currentFreq : nextAvailable;
        deletions += currentFreq - assigned;
        
        // Update next available (can't go below 0)
        nextAvailable = assigned - 1;
        if (nextAvailable < 0) {
            nextAvailable = 0;
        }
    }
    
    return deletions;
}

int main() {
    char s[100001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    int result = solution(s);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n + k log k)

O(n) to count frequencies, O(k log k) to sort k unique characters, where k ≤ 26

⚡ Linearithmic

Space Complexity

O(k)

Space for frequency map and sorted list of at most 26 characters

✓ Linear Space

89.5K Views

Medium Frequency

~15 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy with Sorting — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler