Minimum characters required to be removed to make frequency of each character unique
Given string str, the task is to find the minimum count of characters that need to be deleted from the string such that the frequency of each character of the string is unique.
Examples:
Input: str = “ceabaacb”
Output: 2
Explanation:
The frequencies of each distinct character are as follows:
c —> 2
e —> 1
a —> 3
b —> 2
Possible ways to make frequency of each character unique by minimum number of moves are:
- Removing both occurrences of ‘c’ modifies str to “eabaab”
- Removing an occurrence of ‘c’ and ‘e’ modifies str to “abaacb”
Therefore, the minimum removals required is 2.
Input: S = “abbbcccd”
Output: 2
Approach: The problem can be solved using Greedy technique. The idea is to use Map and Priority Queue. Follow the steps below to solve the problem:
- Initialize a Map, say mp, to store the frequency of each distinct character of the string.
- Initialize a variable, say cntChar to store the count of characters required to be removed to make frequency of each character of the string unique.
- Create a priority_queue, say pq to store the frequency of each character such that the largest frequency obtained is present at the top of the priority queue pq.
- Iterate over the priority_queue until pq is empty and check if the topmost of element of pq is equal to the second topmost element of pq or not. If found to be true, then decrement the value of topmost element of pq by 1 and increment the value of cntChar by 1.
- Otherwise, pop the topmost element of pq.
- Finally, print the value of cntChar.
Below is the implementation of the above approach:
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to find the minimum count of // characters required to be deleted to make // frequencies of all characters unique int minCntCharDeletionsfrequency(string& str, int N) { // Stores frequency of each // distinct character of str unordered_map< char , int > mp; // Store frequency of each distinct // character such that the largest // frequency is present at the top priority_queue< int > pq; // Stores minimum count of characters // required to be deleted to make // frequency of each character unique int cntChar = 0; // Traverse the string for ( int i = 0; i < N; i++) { // Update frequency of str[i] mp[str[i]]++; } // Traverse the map for ( auto it : mp) { // Insert current // frequency into pq pq.push(it.second); } // Traverse the priority_queue while (!pq.empty()) { // Stores topmost // element of pq int frequent = pq.top(); // Pop the topmost element pq.pop(); // If pq is empty if (pq.empty()) { // Return cntChar return cntChar; } // If frequent and topmost // element of pq are equal if (frequent == pq.top()) { // If frequency of the topmost // element is greater than 1 if (frequent > 1) { // Insert the decremented // value of frequent pq.push(frequent - 1); } // Update cntChar cntChar++; } } return cntChar; } // Driver Code int main() { string str = "abbbcccd" ; // Stores length of str int N = str.length(); cout << minCntCharDeletionsfrequency( str, N); return 0; } |
Java
// Java program to implement // the above approach import java.util.*; class GFG{ // Function to find the minimum count of // characters required to be deleted to make // frequencies of all characters unique static int minCntCharDeletionsfrequency( char [] str, int N) { // Stores frequency of each // distinct character of str HashMap<Character, Integer> mp = new HashMap<>(); // Store frequency of each distinct // character such that the largest // frequency is present at the top PriorityQueue<Integer> pq = new PriorityQueue<>((x, y) -> Integer.compare(y, x)); // Stores minimum count of characters // required to be deleted to make // frequency of each character unique int cntChar = 0 ; // Traverse the String for ( int i = 0 ; i < N; i++) { // Update frequency of str[i] if (mp.containsKey(str[i])) { mp.put(str[i], mp.get(str[i]) + 1 ); } else { mp.put(str[i], 1 ); } } // Traverse the map for (Map.Entry<Character, Integer> it : mp.entrySet()) { // Insert current // frequency into pq pq.add(it.getValue()); } // Traverse the priority_queue while (!pq.isEmpty()) { // Stores topmost // element of pq int frequent = pq.peek(); // Pop the topmost element pq.remove(); // If pq is empty if (pq.isEmpty()) { // Return cntChar return cntChar; } // If frequent and topmost // element of pq are equal if (frequent == pq.peek()) { // If frequency of the topmost // element is greater than 1 if (frequent > 1 ) { // Insert the decremented // value of frequent pq.add(frequent - 1 ); } // Update cntChar cntChar++; } } return cntChar; } // Driver Code public static void main(String[] args) { String str = "abbbcccd" ; // Stores length of str int N = str.length(); System.out.print(minCntCharDeletionsfrequency( str.toCharArray(), N)); } } // This code is contributed by Rajput-Ji |
Python3
# Python3 program to implement # the above approach # Function to find the minimum count of # characters required to be deleted to make # frequencies of all characters unique def minCntCharDeletionsfrequency( str , N): # Stores frequency of each # distinct character of str mp = {} # Store frequency of each distinct # character such that the largest # frequency is present at the top pq = [] # Stores minimum count of characters # required to be deleted to make # frequency of each character unique cntChar = 0 # Traverse the string for i in range (N): # Update frequency of str[i] mp[ str [i]] = mp.get( str [i], 0 ) + 1 # Traverse the map for it in mp: # Insert current # frequency into pq pq.append(mp[it]) pq = sorted (pq) # Traverse the priority_queue while ( len (pq) > 0 ): # Stores topmost # element of pq frequent = pq[ - 1 ] # Pop the topmost element del pq[ - 1 ] # If pq is empty if ( len (pq) = = 0 ): # Return cntChar return cntChar # If frequent and topmost # element of pq are equal if (frequent = = pq[ - 1 ]): # If frequency of the topmost # element is greater than 1 if (frequent > 1 ): # Insert the decremented # value of frequent pq.append(frequent - 1 ) # Update cntChar cntChar + = 1 pq = sorted (pq) return cntChar # Driver Code if __name__ = = '__main__' : str = "abbbcccd" # Stores length of str N = len ( str ) print (minCntCharDeletionsfrequency( str , N)) # This code is contributed by mohit kumar 29 |
C#
// C# program to implement // the above approach using System; using System.Collections.Generic; class GFG{ // Function to find the minimum count of // characters required to be deleted to make // frequencies of all characters unique static int minCntCharDeletionsfrequency( char [] str, int N) { // Stores frequency of each // distinct character of str Dictionary< char , int > mp = new Dictionary< char , int >(); // Store frequency of each distinct // character such that the largest // frequency is present at the top List< int > pq = new List< int >(); // Stores minimum count of characters // required to be deleted to make // frequency of each character unique int cntChar = 0; // Traverse the String for ( int i = 0; i < N; i++) { // Update frequency of str[i] if (mp.ContainsKey(str[i])) { mp[str[i]]++; } else { mp.Add(str[i], 1); } } // Traverse the map foreach (KeyValuePair< char , int > it in mp) { // Insert current // frequency into pq pq.Add(it.Value); } pq.Sort(); pq.Reverse(); // Traverse the priority_queue while (pq.Count != 0) { // Stores topmost // element of pq pq.Sort(); pq.Reverse(); int frequent = pq[0]; // Pop the topmost element pq.RemoveAt(0); // If pq is empty if (pq.Count == 0) { // Return cntChar return cntChar; } // If frequent and topmost // element of pq are equal if (frequent == pq[0]) { // If frequency of the topmost // element is greater than 1 if (frequent > 1) { // Insert the decremented // value of frequent pq.Add(frequent - 1); pq.Sort(); // pq.Reverse(); } // Update cntChar cntChar++; } } return cntChar; } // Driver Code public static void Main(String[] args) { String str = "abbbcccd" ; // Stores length of str int N = str.Length; Console.Write(minCntCharDeletionsfrequency( str.ToCharArray(), N)); } } // This code is contributed by shikhasingrajput |
Javascript
<script> // Javascript program to implement // the above approach // Function to find the minimum count of // characters required to be deleted to make // frequencies of all characters unique function minCntCharDeletionsfrequency(str,N) { // Stores frequency of each // distinct character of str let mp = new Map(); // Store frequency of each distinct // character such that the largest // frequency is present at the top let pq =[]; // Stores minimum count of characters // required to be deleted to make // frequency of each character unique let cntChar = 0; // Traverse the String for (let i = 0; i < N; i++) { // Update frequency of str[i] if (mp.has(str[i])) { mp.set(str[i], mp.get(str[i]) + 1); } else { mp.set(str[i], 1); } } // Traverse the map for (let [key, value] of mp.entries()) { // Insert current // frequency into pq pq.push(value); } pq.sort( function (a,b){ return b-a;}); // Traverse the priority_queue while (pq.length!=0) { // Stores topmost // element of pq let frequent = pq[0]; // Pop the topmost element pq.shift(); // If pq is empty if (pq.length==0) { // Return cntChar return cntChar; } // If frequent and topmost // element of pq are equal if (frequent == pq[0]) { // If frequency of the topmost // element is greater than 1 if (frequent > 1) { // Insert the decremented // value of frequent pq.push(frequent - 1); pq.sort( function (a,b){ return b-a;}); } // Update cntChar cntChar++; } } return cntChar; } // Driver Code let str = "abbbcccd" ; let N = str.length; document.write(minCntCharDeletionsfrequency( str.split( "" ), N)); // This code is contributed by unknown2108 </script> |
2
Time Complexity:O(N)
Auxiliary Space:O(1)
Approach 2: Decrement each duplicate until it is unique
we will first start by calculating the frequency of each character. Then, in this approach, we will iterate over the frequencies, and for each frequency, we will check to see if this frequency has already been seen. If it has, we will decrease the frequency until it becomes unique or zero (signifying that we have deleted all occurrences of this character).
- Store the frequency for each character in the given string s in a frequency array called fre (of size 26 for each character). We store the frequency of each character c at index c-‘a’.
- initialize the cnt to 0 , which stores the count of characters that need to be deleted. Also, initialize a HashSet seen that stores the frequencies that we have occupied.
- Iterate over the characters from a to z as 0 to 25, for each character:
1. keep decrementing the frequency of character until it is not present in seen and increment the cnt each time we decrement frequency.
2. when the frequency becomes unique (or zero) insert it into the set seen.
C++
#include <bits/stdc++.h> using namespace std; int minDeletions(string s) { // initializing "fre" vector to get count of frequency // of each character vector< int > fre(26, 0); set< int > seen; // initialize a seen hashset to store // occupied frequencies int cnt = 0; for ( int i = 0; i < s.length(); i++) { fre[s[i] - 'a' ]++; } for ( int i = 0; i < 26; i++) { // if fre[i] is already present in seen set, we // decrement fre[i] and increment cnt; while (fre[i] && seen.find(fre[i]) != seen.end()) { fre[i]--; cnt++; } seen.insert( fre[i]); // when frequency of characters become // unique insert it into seen set. } return cnt; } int main() { string s = "abbbcccd" ; cout << minDeletions(s) << endl; return 0; } |
Java
// Java program to implement // the above approach import java.util.*; class GFG{ // Function to find the minimum count of // characters required to be deleted to make // frequencies of all characters unique static int minCntCharDeletionsfrequency( char [] str, int N) { HashMap<Character, Integer> map = new HashMap<Character, Integer>(); int count = 0 ; // get the frequencies of each letter in the string for ( char c: str){ if (!map.containsKey(c)){ map.put(c, 1 ); } else { map.put(c, map.get(c) + 1 ); } } // store the frequencies into an arraylist ArrayList<Integer> frequencies = new ArrayList<>(map.values()); // initialize hashset HashSet<Integer> set = new HashSet<Integer>(); for ( int value: frequencies){ if (!set.contains(value)){ set.add(value); } else { while (value > 0 && set.contains(value)){ value--; count++; } set.add(value); } } return count; } // Driver Code public static void main(String[] args) { String str = "abbbcccd" ; // Stores length of str int N = str.length(); System.out.print(minCntCharDeletionsfrequency( str.toCharArray(), N)); } } // This code is contributed by Rajput-Ji |
Python3
# Python3 program to implement # the above approach # Function to find the minimum count of # characters required to be deleted to make # frequencies of all characters unique def minCntCharDeletionsfrequency(s ,n) - > int : legend = {} freq = [ False for i in range (n + 1 )] for c in s: if c not in legend: legend = 1 else : legend + = 1 res = 0 for key, val in legend.items(): #Check uniqueness of each frequency while freq[val] and val > 0 : #If we have a non-unique frequency which still exists, then we must "remove" one val - = 1 res + = 1 freq[val] = True return res # Driver Code if __name__ = = '__main__' : str = "abbbcccd" # Stores length of str N = len ( str ) print (minCntCharDeletionsfrequency( str , N)) # This code is contributed by isha307. |
C#
// C# program to implement // the above approach using System; using System.Collections.Generic; class GFG { // Function to find the minimum count of // characters required to be deleted to make // frequencies of all characters unique static int minCntCharDeletionsfrequency( char [] str, int N) { Dictionary< char , int > map = new Dictionary< char , int >(); int count = 0; // get the frequencies of each letter in the string foreach ( char c in str) { if (!map.ContainsKey(c)) { map.Add(c, 1); } else { map++; } } // store the frequencies into a list List< int > frequencies = new List< int >(map.Values); // initialize hashset HashSet< int > set = new HashSet< int >(); foreach ( int value in frequencies) { if (! set .Contains(value)) { set .Add(value); } else { int tempValue = value; while (tempValue > 0 && set .Contains(tempValue)) { tempValue--; count++; } set .Add(tempValue); } } return count; } // Driver Code public static void Main( string [] args) { string str = "abbbcccd" ; // Stores length of str int N = str.Length; Console.Write(minCntCharDeletionsfrequency( str.ToCharArray(), N)); } } // This code is contributed by phasing17 |
Javascript
// JavaScript program to implement // the above approach function minDeletions(s) { // initializing "fre" vector to get count // of frequency of each character let fre = Array(26).fill(0); // initialize a seen hashset to store // occupied frequencies let seen = new Set(); let cnt = 0; for (let i = 0; i < s.length; i++) { fre[s.charCodeAt(i) - 'a' .charCodeAt(0)]++; } for (let i = 0; i < 26; i++) { // if fre[i] is already present in seen set, we // decrement fre[i] and increment cnt; while (fre[i] && seen.has(fre[i])) { fre[i]--; cnt++; } // when frequency of characters become // unique insert it into seen set. seen.add(fre[i]); } return cnt; } let s = "abbbcccd" ; console.log(minDeletions(s)); // This code is contributed by Prasad Kandekar(prasad264) |
Output
2
Time Complexity: O(N)
Auxiliary Space: O(N)