Minimum Deletions To Get a Unique Count Of Characters

Find the minimum number of deletions required to get a unique count of every character.

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:

class Program
{
    static void Main(string[] args)
    {
        string input = "ccaaffddecee";
        int result = Approach1(input);
        //result is 6
        input = "example";
        result = Approach1(input);
        //result is 4
    }
    static int Approach1(string input)
    {
        int numOfDeletion = 0;
        List<int> numOfChrs = new List<int>();
        //array of distinct characters
        IEnumerable<char> distinctChrs = input.Distinct();
        foreach (var chr in distinctChrs)
        {
            //count the number of characters in the string
            int countChr = input.Count(x => x.Equals(chr));
            while (countChr != 0 && numOfChrs.Contains(countChr))
            {
                countChr--;
                numOfDeletion++;
            }
            //add the count number in the list
            numOfChrs.Add(countChr);
        }
        return numOfDeletion;
    }
}

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#:

class Program
{
    static void Main(string[] args)
    {
        string input = "ccaaffddecee";
        int result = Approach2(input);
        //result is 6
        input = "example";
        result = Approach2(input);
        //result is 4
    }
    static int Approach2(string input)
    {
        int numOfDeletion = 0;
        List<int> numOfChrs = new List<int>();
        //array of distinct characters
        IEnumerable<char> distinctChrs = input.Distinct();
        foreach (char chr in distinctChrs)
        {
            //count the number of characters in the string
            int countChr = input.Count(x => x.Equals(chr));
            numOfDeletion += DeleteChrs(numOfChrs, countChr, 0);
        }
        return numOfDeletion;
    }
    static int DeleteChrs(List<int> numOfChrs, int countChr, int numOfDeletion)
    {
        //end condition of the recursion
        if (countChr == 0)
            return numOfDeletion;

        //call resursively if the count is still not unique
        if (numOfChrs.Any(x => x.Equals(countChr)))
            return DeleteChrs(numOfChrs, --countChr, ++numOfDeletion);

        //add the count number in the list
        numOfChrs.Add(countChr);
        return numOfDeletion;
    }
}