# Minimum Deletions to Make Character Frequencies Unique
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-deletions-to-make-character-frequencies-unique)
Canonical: https://scaleengineer.com/dsa/problems/minimum-deletions-to-make-character-frequencies-unique
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Hash Table, String
**Companies:** [American Express](https://scaleengineer.com/companies/american-express), [ConsultAdd](https://scaleengineer.com/companies/consultadd), [smartnews](https://scaleengineer.com/companies/smartnews)
---
## 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`.

**Example 1:**

**Input:** s = "aab"
**Output:** 0
**Explanation:** `s` is already good.

**Example 2:**

**Input:** s = "aaabbbcc"
**Output:** 2
**Explanation:** You can delete two 'b's resulting in the good string "aaabcc".
Another way it to delete one 'b' and one 'c' resulting in the good string "aaabbc".

**Example 3:**

**Input:** s = "ceabaacb"
**Output:** 2
**Explanation:** You can delete both 'c's resulting in the good string "eabaab".
Note that we only care about characters that are still in the string at the end (i.e. frequency of 0 is ignored).

**Constraints:**

* `1 <= s.length <= 105`
* `s` contains only lowercase English letters.

# Approaches
## Greedy Approach with a Frequency-Tracking Array
This approach first calculates the frequency of each character. Then, it iterates through these frequencies, resolving duplicates greedily. A boolean array is used to keep track of which frequency values have already been taken. When a duplicate frequency is found, it's decremented until an unused frequency value is found. The number of decrements is counted as the number of deletions.
**Time:** O(N), where N is the length of the string. Counting frequencies is O(N). The conflict resolution part involves iterating 26 times. The inner `while` loop's total iterations across all frequencies is bounded by the total number of deletions, which cannot exceed N. Thus, the overall complexity is dominated by the initial scan of the string. · **Space:** O(N), where N is the length of the input string. The `occupied` boolean array can have a size up to `N+1` if a single character appears N times. The frequency count array is O(1).
**Pros:** Conceptually simple greedy approach.; Fast array lookups (`occupied[freq]`) provide good performance for the conflict resolution part.
**Cons:** High space complexity of O(N), which can be large if the input string is long, potentially leading to memory issues for constraints like N=10^5.
### Explanation
1.  **Count Character Frequencies:** Create an integer array, say `charCounts`, of size 26 to store the frequency of each lowercase English letter. Iterate through the input string `s` and populate this array.
2.  **Track Used Frequencies:** Create a boolean array, `occupied`, of size `s.length() + 1`. This array will mark which frequency values are already in use by a character. `occupied[f]` will be `true` if a character has frequency `f`, and `false` otherwise.
3.  **Resolve Conflicts:** Initialize a variable `deletions = 0`. Iterate through the `charCounts` array. For each character's frequency `freq`:
    *   Check if the current `freq` is already occupied by another character (i.e., `occupied[freq]` is true).
    *   If it is, and `freq` is greater than 0, decrement `freq` and increment `deletions`. Repeat this until an unoccupied frequency is found or the frequency becomes 0.
    *   If the final `freq` is greater than 0, mark it as occupied by setting `occupied[freq] = true`.
4.  **Return Result:** The total value of `deletions` is the minimum required to make the string "good".

```java
class Solution {
    public int minDeletions(String s) {
        int[] charCounts = new int[26];
        for (char c : s.toCharArray()) {
            charCounts[c - 'a']++;
        }

        boolean[] occupied = new boolean[s.length() + 1];
        int deletions = 0;

        for (int i = 0; i < 26; i++) {
            int freq = charCounts[i];
            while (freq > 0 && occupied[freq]) {
                freq--;
                deletions++;
            }
            if (freq > 0) {
                occupied[freq] = true;
            }
        }
        return deletions;
    }
}
```
### Algorithm
- Create an integer array `charCounts` of size 26 and initialize to 0.
- Iterate through string `s`, incrementing `charCounts[c - 'a']` for each character `c`.
- Create a boolean array `occupied` of size `s.length() + 1`.
- Initialize `deletions = 0`.
- For each `count` in `charCounts`:
    - While `count > 0` and `occupied[count]` is true:
        - Decrement `count`.
        - Increment `deletions`.
    - If `count > 0`, set `occupied[count]` to true.
- Return `deletions`.

## Greedy Approach with a HashSet
This approach is a space-optimized version of the previous one. Instead of a large boolean array, it uses a `HashSet` to store the frequencies that are already in use. The logic remains the same: count character frequencies, then iterate through them, decrementing any frequency that's already in the set until an unused value is found.
**Time:** O(N). Counting frequencies takes O(N). The second part involves iterating through 26 counts. The total number of `contains` checks and decrements in the `while` loop is bounded by N, making the overall time complexity O(N). · **Space:** O(1). The `charCounts` array is of constant size 26. The `usedFrequencies` set will store at most 26 unique frequencies, as there are only 26 lowercase letters. Thus, the space is constant.
**Pros:** Optimal space complexity of O(1).; Maintains the simple and intuitive greedy logic.
**Cons:** `HashSet` operations have a slightly higher constant factor overhead compared to direct array access.
### Explanation
1.  **Count Character Frequencies:** Just like the first approach, use an integer array of size 26 to count the occurrences of each character in the string `s`.
2.  **Track Used Frequencies with a Set:** Create a `HashSet<Integer>`, say `usedFrequencies`, to store the unique frequencies we decide to keep.
3.  **Resolve Conflicts:** Initialize `deletions = 0`. Iterate through the 26 possible character counts. For each non-zero frequency `freq`:
    *   Use a `while` loop to check if `freq` is already present in the `usedFrequencies` set.
    *   As long as it is present and `freq > 0`, decrement `freq` and increment `deletions`. This simulates deleting a character to get a new, hopefully unique, frequency.
    *   Once an unused frequency is found (or `freq` becomes 0), if `freq > 0`, add it to the `usedFrequencies` set to reserve it.
4.  **Return Result:** The accumulated `deletions` count is the minimum required.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int minDeletions(String s) {
        int[] charCounts = new int[26];
        for (char c : s.toCharArray()) {
            charCounts[c - 'a']++;
        }

        Set<Integer> usedFrequencies = new HashSet<>();
        int deletions = 0;

        for (int count : charCounts) {
            int freq = count;
            while (freq > 0 && usedFrequencies.contains(freq)) {
                freq--;
                deletions++;
            }
            if (freq > 0) {
                usedFrequencies.add(freq);
            }
        }
        return deletions;
    }
}
```
### Algorithm
- Create an integer array `charCounts` of size 26 and initialize to 0.
- Iterate through string `s`, incrementing `charCounts[c - 'a']` for each character `c`.
- Create a `HashSet<Integer>` named `usedFrequencies`.
- Initialize `deletions = 0`.
- For each `count` in `charCounts`:
    - While `count > 0` and `usedFrequencies.contains(count)` is true:
        - Decrement `count`.
        - Increment `deletions`.
    - If `count > 0`, add `count` to `usedFrequencies`.
- Return `deletions`.

## Greedy Approach with Sorting
This approach also starts by counting character frequencies. Instead of using an auxiliary data structure to track used frequencies on the fly, it sorts the frequencies. By processing from the largest frequency to the smallest, we can greedily ensure that when we adjust a frequency, we make it as large as possible while still being unique. This guarantees a minimum number of deletions.
**Time:** O(N). Counting frequencies is O(N). Sorting an array of size 26 is `O(26 log 26)`, which is constant time, O(1). The final loop runs at most 25 times, which is also O(1). The dominant step is the initial frequency counting. · **Space:** O(1). We only use a constant-size array (`counts`) for frequencies. The sorting is done in-place.
**Pros:** Optimal time and space complexity.; Avoids the overhead of hash set operations, potentially leading to better performance due to direct array manipulations after a one-time sort of a very small array.
**Cons:** The logic involving sorting and then adjusting might be slightly less direct to reason about than the HashSet approach for some.
### Explanation
1.  **Count Frequencies:** Use an integer array of size 26 to count the frequency of each character.
2.  **Sort Frequencies:** Sort the frequency array. Sorting in ascending order is convenient for the iteration logic that follows.
3.  **Greedily Adjust Frequencies:** Iterate through the sorted frequencies from largest to smallest (i.e., from right to left in the sorted array). The frequency at `counts[i+1]` sets the upper bound for what `counts[i]` can be. 
    *   Initialize `deletions = 0`.
    *   Iterate from `i = 24` down to `0`.
    *   If `counts[i]` is 0, all smaller frequencies are also 0, so we can stop.
    *   If `counts[i]` is greater than or equal to `counts[i+1]`, it's a conflict. We must reduce `counts[i]` to be at most `counts[i+1] - 1`. To minimize deletions, we set its new value to exactly `counts[i+1] - 1` (or 0 if `counts[i+1]` is 0 or 1).
    *   The number of deletions for the current character is the difference between its original frequency and its new, adjusted frequency.
4.  **Return Result:** The total deletions are the minimum required.

```java
import java.util.Arrays;

class Solution {
    public int minDeletions(String s) {
        int[] counts = new int[26];
        for (char c : s.toCharArray()) {
            counts[c - 'a']++;
        }

        // Sort frequencies in ascending order
        Arrays.sort(counts);

        int deletions = 0;
        // Iterate from the second-to-last element (which holds one of the largest frequencies)
        for (int i = 24; i >= 0; i--) {
            // If current frequency is 0, all previous are also 0, so we can stop
            if (counts[i] == 0) {
                break;
            }
            // If current frequency is same or larger than the next one
            if (counts[i] >= counts[i+1]) {
                int originalFreq = counts[i];
                // The new frequency must be one less than the next one, or 0
                counts[i] = Math.max(0, counts[i+1] - 1);
                deletions += originalFreq - counts[i];
            }
        }
        return deletions;
    }
}
```
### Algorithm
- Create an integer array `counts` of size 26 and count character frequencies from `s`.
- Sort the `counts` array in ascending order.
- Initialize `deletions = 0`.
- Iterate from `i = 24` down to `0`.
- If `counts[i] == 0`, break the loop as all preceding frequencies will also be zero.
- If `counts[i] >= counts[i+1]` (i.e., the current frequency is not smaller than the next larger one):
    - Calculate the number of deletions needed for the current frequency: `deletions += counts[i] - Math.max(0, counts[i+1] - 1)`.
    - Update the current frequency to its new valid value: `counts[i] = Math.max(0, counts[i+1] - 1)`.
- Return `deletions`.

# Solutions
### Java

```java
class Solution {
public
  int minDeletions(String s) {
    int[] cnt = new int[26];
    for (int i = 0; i < s.length(); ++i) {
      ++cnt[s.charAt(i) - 'a'];
    }
    Arrays.sort(cnt);
    int ans = 0;
    for (int i = 24; i >= 0; --i) {
      while (cnt[i] >= cnt[i + 1] && cnt[i] > 0) {
        --cnt[i];
        ++ans;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minDeletions(string s) {
    vector<int> cnt(26);
    for (char &c : s)
      ++cnt[c - 'a'];
    sort(cnt.rbegin(), cnt.rend());
    int ans = 0;
    for (int i = 1; i < 26; ++i) {
      while (cnt[i] >= cnt[i - 1] && cnt[i] > 0) {
        --cnt[i];
        ++ans;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def minDeletions(self, s: str) -> int: cnt = Counter(s) ans, pre = 0, inf for v in sorted(cnt . values(), reverse=True): if pre == 0: ans += v elif v >= pre: ans += v - pre + 1 pre -= 1 else: pre = v return ans

```