Minimum Deletions To Get a Unique Count Of Characters

Problem Statement
 
Given a string consisting of N lowercase characters, find the minimum number of characters that must be deleted to obtain a string in which every character occurs a unique number of times. Here are some examples, input string "ccaaffddecee" would result to 6 since, initially the string had c-3, a-2, f-2, d-2, e-3 in order of appearance and the final string will have c-3, a-2, f-1. so 6 characters got deleted namely, f-1, d-2, e-3. Similarly for the input string "example" the result would be 4 deletions.
 
Approach 1
 
The first approach to solve this problem would be by using nested loops, one over every unique character in the input string and then, we check whether the character's count is unique then, we add it to our array/list or else we keep reducing the character's count by one until reached to zero.
 
Time Complexity - O(N^2)
Space Complexity - O(N)
 
Here's a sample code in C# that demonstrates this algorithm:
  1. class Program  
  2. {  
  3.     static void Main(string[] args)  
  4.     {  
  5.         string input = "ccaaffddecee";  
  6.         int result = Approach1(input);  
  7.         //result is 6  
  8.         input = "example";  
  9.         result = Approach1(input);  
  10.         //result is 4  
  11.     }  
  12.     static int Approach1(string input)  
  13.     {  
  14.         int numOfDeletion = 0;  
  15.         List<int> numOfChrs = new List<int>();  
  16.         //array of distinct characters  
  17.         IEnumerable<char> distinctChrs = input.Distinct();  
  18.         foreach (var chr in distinctChrs)  
  19.         {  
  20.             //count the number of characters in the string  
  21.             int countChr = input.Count(x => x.Equals(chr));  
  22.             while (countChr != 0 && numOfChrs.Contains(countChr))  
  23.             {  
  24.                 countChr--;  
  25.                 numOfDeletion++;  
  26.             }  
  27.             //add the count number in the list   
  28.             numOfChrs.Add(countChr);  
  29.         }  
  30.         return numOfDeletion;  
  31.     }  
  32. }  
Approach 2
 
The approach is very similar to the above approach but in a recursive way. By just using the logic of the second loop in a separate recursive method we can get the number of deletions needed. The rest of with time and space complexities are the same as in the above approach. Below is a code sample for this approach in C#:
  1. class Program  
  2. {  
  3.     static void Main(string[] args)  
  4.     {  
  5.         string input = "ccaaffddecee";  
  6.         int result = Approach2(input);  
  7.         //result is 6  
  8.         input = "example";  
  9.         result = Approach2(input);  
  10.         //result is 4  
  11.     }  
  12.     static int Approach2(string input)  
  13.     {  
  14.         int numOfDeletion = 0;  
  15.         List<int> numOfChrs = new List<int>();  
  16.         //array of distinct characters  
  17.         IEnumerable<char> distinctChrs = input.Distinct();  
  18.         foreach (char chr in distinctChrs)  
  19.         {  
  20.             //count the number of characters in the string  
  21.             int countChr = input.Count(x => x.Equals(chr));  
  22.             numOfDeletion += DeleteChrs(numOfChrs, countChr, 0);  
  23.         }  
  24.         return numOfDeletion;  
  25.     }  
  26.     static int DeleteChrs(List<int> numOfChrs, int countChr, int numOfDeletion)  
  27.     {  
  28.         //end condition of the recursion  
  29.         if (countChr == 0)  
  30.             return numOfDeletion;  
  31.   
  32.         //call resursively if the count is still not unique  
  33.         if (numOfChrs.Any(x => x.Equals(countChr)))  
  34.             return DeleteChrs(numOfChrs, --countChr, ++numOfDeletion);  
  35.   
  36.         //add the count number in the list   
  37.         numOfChrs.Add(countChr);  
  38.         return numOfDeletion;  
  39.     }  
  40. }  


Next Recommended Reading Unique Array Items In C#