Solution For Minimum Deletions To Make Character Frequencies Unique

Problem Statement:

Given a string s consisting of n lowercase letters, you have to delete the minimum number of characters from s to make the frequency of each character unique. Return the minimum number of deletions needed.

Example:
Input: s = “aab”
Output: 0
Explanation: You will never get such a string after deleting any characters.
Input: s = “aaabbbcc”
Output: 2
Explanation: You can delete two ‘b’s resulting in the string “aaabcc”. Now there aren’t any repeating characters.

Solution Approach:

• Create a hashmap to count the frequency of all characters in the given string.
• Create a set to maintain the unique frequencies of characters in the hashmap.
• Iterate through the hashmap and check if the frequency of each character is unique. If not, calculate the number of deletions required to make it unique and add it to the answer.
• Return the answer.

Code:

class Solution {
public:
int minDeletions(string s) {
unordered_map freq_map;
for(char ch: s) freq_map[ch]++;
unordered_set freq_set;

    int ans = 0;
    for(auto p: freq_map) {
        int freq = p.second;
        while(freq_set.count(freq)) {
            ans++;
            freq--;
        }
        if(freq > 0) freq_set.insert(freq);
    }
    return ans;
}

};

In the above code, we first create a frequency hashmap (freq_map) to store the count of each character in the string s.

We then create an unordered set (freq_set) to maintain a record of unique frequencies of all characters in the hashmap.

We then loop through each character in the hashmap and check if its frequency is unique or not. If the frequency is not unique, we calculate the number of deletions required to make it unique and add this to our answer (ans). We do this by reducing the frequency of the character until it becomes unique. This is done using the while loop.

Finally, if the frequency of the character is greater than 0, we insert this unique frequency into our set (freq_set).

The time complexity of the above code is O(n log n) since we need to perform deletion, which in the worst case may take O(n log n) time.

Step by Step Implementation For Minimum Deletions To Make Character Frequencies Unique

class Solution {
    public int minDeletions(String s) {
        int[] counts = new int[26];
        for (char c : s.toCharArray()) {
            counts[c-'a']++;
        }
        Arrays.sort(counts);
        int ans = 0;
        for (int i = 1; i < 26; ++i) {
            if (counts[i] == 0) break;
            int take = Math.min(counts[i], counts[i-1]-1);
            counts[i] -= take;
            ans += take;
        }
        return ans;
    }
}

class Solution:
    def minDeletions(self, s: str) -> int:
        # create a list of frequencies for each character
        freq = [0] * 26
        for c in s:
            freq[ord(c) - ord('a')] += 1
            
        # sort the frequencies in reverse order
        freq.sort(reverse=True)
        
        # keep track of the number of deletions needed
        num_deletions = 0
        
        # iterate over the frequencies in reverse order
        for i in range(1, len(freq)):
            # if the current frequency is equal to the previous frequency,
            # we need to delete it
            if freq[i] == freq[i-1]:
                # increment the number of deletions
                num_deletions += 1
                # set the current frequency to the next highest frequency
                freq[i] -= 1
                
        return num_deletions

/**
 * @param {string} s
 * @return {number}
 */
var minDeletions = function(s) {
    // create a map to store the frequencies of each character
    let map = {};
    
    // iterate through the string and increment the count for each character
    for (let i = 0; i < s.length; i++) {
        let c = s.charAt(i);
        if (map[c]) {
            map[c]++;
        } else {
            map[c] = 1;
        }
    }
    
    // create an array of the frequencies
    let values = Object.values(map);
    
    // sort the array in descending order
    values.sort((a, b) => b - a);
    
    // iterate through the array and delete characters until all frequencies are unique
    let count = 0;
    for (let i = 0; i < values.length - 1; i++) {
        if (values[i] === values[i + 1]) {
            values[i + 1]--;
            count++;
        }
    }
    
    return count;
};

One possible solution is to keep track of the frequencies of each character in a map, and then iterate through the map to find the minimum number of deletions needed. For each character, we can either delete it or keep it, and we want to minimize the number of deletions overall.

To do this, we can keep track of the number of characters that have been deleted so far, and for each character in the map, we can either delete it or keep it. If we keep it, we add its frequency to the number of deletions. Otherwise, we update the number of deletions to be the minimum of the current number of deletions or the number of deletions plus the character's frequency - 1 (since we need to delete at least one character).

For example, given the input "abbccc", we would have the following map:

a -> 1
b -> 2
c -> 3

We would delete the character 'a', since its frequency is 1 and we need to delete at least one character anyway. For 'b', we would keep it since its frequency is 2. For 'c', we would delete it since its frequency is 3 and we need to delete at least 2 characters anyway. This gives us a total of 3 deletions.

using System; 
  
class GFG { 
      
// Function to find minimum deletions 
static int minDeletions(int[] freq, int n) 
{ 
    int min_deletions = 0; 
  
    // To keep track of visited frequencies 
    bool[] visited = new bool[n]; 
    for (int i = 0; i < n; i++) 
        visited[i] = false; 
  
    // Sort the frequencies in non-increasing order 
    Array.Sort(freq); 
  
    // Start traversing the sorted array 
    for (int i = n - 1; i >= 0;) { 
        // If the current element is visited 
        // or it's frequency is 0, then 
        // continue with next element 
        if (visited[i] || freq[i] == 0) { 
            i--; 
            continue; 
        } 
  
        // If the (i+1)th element has same 
        // frequency as that of current 
        // element, then increment count of 
        // deletions and make the (i+1)th 
        // element as visited 
        if ((i - 1 >= 0) && (freq[i] == freq[i - 1])) { 
            min_deletions++; 
            visited[i - 1] = true; 
            i--; 
        } 
  
        // If the (i+1)th element has frequency 
        // less than that of current element, 
        // then increment the frequency of 
        // (i+1)th element by one and make it 
        // visited. Note that the order is 
        // maintained as the frequencies array 
        // is sorted in non-increasing order 
        else if ((i - 1 >= 0) && (freq[i] > freq[i - 1])) { 
            freq[i - 1]++; 
            min_deletions++; 
            visited[i - 1] = true; 
        } 
  
        // If the (i+1)th element has frequency 0, 
        // then increment the frequency of 
        // current element by one 
        else if (freq[i] > 0) { 
            freq[i]--; 
            min_deletions++; 
        } 
    } 
    return min_deletions; 
} 
  
// Driver Code 
public static void Main() 
{ 
    int[] freq = { 2, 2, 1, 1, 1, 2, 2 }; 
    int n = freq.Length; 
  
    Console.Write(minDeletions(freq, n)); 
} 
} 
  
// This code is contributed by vt_m