Code Implementation

from collections import Counter

class Solution:
    def minDeletions(self, s: str) -> int:
        freq = Counter(s)
        used = set()
        deletions = 0
        for char, f in freq.items():
            while f > 0 and f in used:
                f -= 1
                deletions += 1
            used.add(f)
        return deletions
      

#include <unordered_map>
#include <unordered_set>
#include <string>
using namespace std;

class Solution {
public:
    int minDeletions(string s) {
        unordered_map<char, int> freq;
        for (char c : s) freq[c]++;
        unordered_set<int> used;
        int deletions = 0;
        for (auto it : freq) {
            int f = it.second;
            while (f > 0 && used.count(f)) {
                f--;
                deletions++;
            }
            used.insert(f);
        }
        return deletions;
    }
};
      

import java.util.*;

class Solution {
    public int minDeletions(String s) {
        int[] freq = new int[26];
        for (char c : s.toCharArray()) freq[c - 'a']++;
        Set<Integer> used = new HashSet<>();
        int deletions = 0;
        for (int f : freq) {
            while (f > 0 && used.contains(f)) {
                f--;
                deletions++;
            }
            if (f > 0) used.add(f);
        }
        return deletions;
    }
}
      

var minDeletions = function(s) {
    let freq = {};
    for (let c of s) freq[c] = (freq[c]||0) + 1;
    let used = new Set();
    let deletions = 0;
    for (let char in freq) {
        let f = freq[char];
        while (f > 0 && used.has(f)) {
            f--;
            deletions++;
        }
        used.add(f);
    }
    return deletions;
};
      

Problem Description

Given a string s, you need to ensure that the frequency of each character in s is unique. In other words, no two different characters can have the same frequency after making deletions. You are allowed to delete any number of characters from s (possibly zero) to achieve this. The task is to return the minimum number of deletions required to make all character frequencies unique.

Constraints:

• Only deletions are allowed; you cannot insert or change characters.
• Each deletion removes exactly one character from the string.
• The solution must ensure that no two characters have the same non-zero frequency.

Thought Process

The core challenge is to ensure that the count (frequency) of each character in the string is unique. If two or more characters have the same frequency, we must delete some characters to make the frequencies distinct.

A naive approach would be to try all possible combinations of deletions, but this is highly inefficient. Instead, we can focus on the frequencies themselves: if two frequencies are the same, we can reduce one of them (by deleting characters) until it becomes unique or zero (removing that character entirely).

The main insight is that we can process the frequencies, and for each one, if it is already used, we decrement it until we find an unused frequency or reach zero. This ensures minimal deletions and guarantees uniqueness.

Solution Approach

• Count character frequencies: Use a hash map or array to count how many times each character appears in the string.
• Track used frequencies: Use a set to keep track of frequencies that have already been assigned to other characters.
• Iterate over frequencies: For each frequency, check if it is already used.
• Reduce frequency if necessary:
  • If the frequency is already in the set, decrement it (simulate deleting a character) and increment the deletions counter.
  • Repeat until the frequency is unique or reaches zero (meaning all characters of that type have been deleted).
• Add the final frequency to the set: After ensuring uniqueness, add the frequency to the set of used frequencies.
• Return the total deletions: After processing all characters, return the number of deletions made.

We use a set for used frequencies because lookups and insertions are O(1), making the algorithm efficient.

Example Walkthrough

Let's consider s = "aaabbbcc".

• Count frequencies: {'a': 3, 'b': 3, 'c': 2}
• Start with an empty set for used frequencies.
• Process 'a' (frequency 3): 3 not used, add 3 to set (used = {3})
• Process 'b' (frequency 3): 3 is used, decrement to 2 (1 deletion), 2 not used, add 2 to set (used = {2,3})
• Process 'c' (frequency 2): 2 is used, decrement to 1 (1 deletion), 1 not used, add 1 to set (used = {1,2,3})
• Total deletions: 1 (for 'b') + 1 (for 'c') = 2

Final frequencies are [3,2,1], all unique. The minimum deletions needed is 2.

Time and Space Complexity

• Brute-force approach:
  • Would involve generating all possible subsets of deletions, which is exponential in the length of the string (O(2^n)).
• Optimized approach:
  • Counting frequencies: O(n), where n is the length of the string.
  • Processing frequencies: O(k^2) in the worst case (where k is the number of unique characters), but since the number of unique characters is limited (at most 26 for lowercase English letters), this is effectively O(1).
  • Space complexity: O(k) for the frequency counter and used set, which is at most 26.

Thus, the solution is linear in the length of the string, with constant extra space for the English alphabet.

Summary

The key to solving this problem efficiently is to focus on character frequencies and ensure uniqueness by decrementing duplicates. By using a set to track used frequencies and only deleting as necessary, we achieve a minimal number of deletions. The approach leverages hash maps and sets for fast lookups, resulting in a simple yet elegant solution that is both time and space efficient.