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