# Minimum Deletions to make the occurrence of each character unique.

Objective: Given a string, your task is to delete the minimum number of characters in the string so that the count of each character is unique.

Example:

```Input = "aaaaabbbbb"
Output: 1
Explanation: In the input string, characters 'a' and 'b', both occur 5 times. You can delete either one 'a' or one 'b' to make their count unique (4 and 5 or 5 and 4).

Input = "abcaabbcdaab"
Output: 0
Explanation:
count of 'a' = 5
count of 'b' = 4
count of 'c' = c
Count of 'd' = 1
All characters count is already unique.

Input = "aaaabbbbccccdddd"
Output: 6
Explanation:
count of 'a' = 4
count of 'b' = 4
count of 'c' = 4
Count of 'd' = 4
Delete 1 'b', 2 'c' and 3 'd' to make unique counts as (4, 3, 2, 1)

```

Approach:

• Construct array count[] which contains a count for each character. Below are the steps to how to construct that array.
• Create an array charCount[] of size 26 and fill with 0.
• Iterate the array and maintain the count of each letter in the array charCount[] so that count of character a, b, c, ,,,,, z will be stored at index 0, 1, 2, ,,,,, 25 respectively.
• Once the iteration is completed copy all the elements with non zero count to array list and convert that list to count[].
• Once count[] is constructed, Sort the count[] in descending order.
• Initialize deletes = 0.
• Iterate the count[] from left to right, for current element i
• Iterate elements from j = i+1 to end and if count[i]==count[j], reduce the count at index j and do deletes++  else break the loop. (array is sorted, so you will not find another index j which is equal to index i).
• Return deletes
• See the walkthrough below for more understanding.
```input= "aabbbccc"
charCount[]  = 2, 3, 3, 0, 0, 0 , , , , , , , , , , 0 (size 26)
count[] = 2, 3, 3
Sort the count[] in descending order
count[] = 3, 3, 2
deletes = 0
3 = 3, so reduce next 3 to 2, deletes = 1
count[] = 3, 2, 2
2=2, so reduce next 2 to 1, deletes = 2
count[] = 3, 2, 1
All counts are unique.
Minimum deletes = 2

Time Complexity: O(n + k^2)
Where k = 26 ( no of letters)

```

Complete Code:

Output:

```Given String: aaaa, Minimum Deletion: 0
Given String: aaabbb, Minimum Deletion: 1
Given String: abcaabbcdaab, Minimum Deletion: 0
Given String: aaaabbbbccccdddd, Minimum Deletion: 6
```

This site uses Akismet to reduce spam. Learn how your comment data is processed.