This post is completed by 3 users

  • 1
 Add to List
Hard

503. 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:

  1. Construct array count[] which contains a count for each character. Below are the steps to how to construct that array.
    1. Create an array charCount[] of size 26 and fill with 0.
    2. 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. 
    3. Once the iteration is completed copy all the elements with non zero count to array list and convert that list to count[]. 
  2. Once count[] is constructed, Sort the count[] in descending order.
  3. Initialize deletes = 0.
  4. Iterate the count[] from left to right, for current element i
    1. 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).
  5. Return deletes
  6. 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)

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

Related Problems: