This post is completed by 1 user
|Add to List|
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.
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)
- 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)
Given String: aaaa, Minimum Deletion: 0 Given String: aaabbb, Minimum Deletion: 1 Given String: abcaabbcdaab, Minimum Deletion: 0 Given String: aaaabbbbccccdddd, Minimum Deletion: 6