Given a string S of length N, the task is to find the minimum number of characters required to be removed such that every distinct character in the string occurs same number of times.
Examples:
Input: S = “abcbccdddd”
Output: 4
Explanation: Removing an occurrence of the characters ‘a’, ‘c’ and two occurrences of ‘d’ modifies the string to “bbccdd”. Therefore, every character in the string occurs same number of times.Input : S = “neveropen”
Output : 5
Explanation: Removing an occurrence of ‘r’, ‘f’, ‘and ‘o’ and removing two occurrences of ‘e’ modifies S to “neveropengks”.
Approach: The idea is to use the multiset and map. Follow the steps below to solve the problem:
- Initialize a map<char, int> say countMap and a multiset<int> say countMultiset to store the frequency of every character.
- Initialize a variable say ans as INT_MAX to store the count of minimum characters to be removed.
- Traverse the string S and increment count of S[i] in countMap.
- Iterate over the map countMap and insert the frequency of the character in countMultiset.
- Find the size of multiset countMultiset and store it in a variable say m.
- Traverse the multiset countMultiset and update the ans as ans = min (ans, (N- (m-i)* (*it)))) and increment the i by 1.
- Finally, after completing the above steps print the answer as ans.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find minimum number of// character removals required to make// frequency of all distinct characters the sameint minimumDeletion(string s, int n){ // Stores the frequency // of each character map<char, int> countMap; // Traverse the string for (int i = 0; i < n; i++) { countMap[s[i]]++; } // Stores the frequency of each // character in sorted order multiset<int> countMultiset; // Traverse the Map for (auto it : countMap) { // Insert the frequency in multiset countMultiset.insert(it.second); } // Stores the count of elements // required to be removed int ans = INT_MAX; int i = 0; // Stores the size of multiset int m = countMultiset.size(); // Traverse the multiset for (auto j : countMultiset) { // Update the ans ans = min(ans, n - (m - i) * j); // Increment i by 1 i++; } // Return return ans;}// Driver Codeint main(){ // Input string S = "neveropen"; int N = S.length(); cout << minimumDeletion(S, N); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;class GFG{// Function to find minimum number of// character removals required to make// frequency of all distinct characters the samestatic int minimumDeletion(String s, int n){ // Stores the frequency // of each character HashMap<Character, Integer> countMap = new HashMap<>(); // Traverse the string for(int i = 0; i < n; i++) { char ch = s.charAt(i); countMap.put(ch, countMap.getOrDefault(ch, 0) + 1); } // Stores the frequency of each // character in sorted order ArrayList<Integer> countMultiset = new ArrayList<>( countMap.values()); Collections.sort(countMultiset); // Stores the count of elements // required to be removed int ans = Integer.MAX_VALUE; int i = 0; // Stores the size of multiset int m = countMultiset.size(); // Traverse the multiset for(int j : countMultiset) { // Update the ans ans = Math.min(ans, n - (m - i) * j); // Increment i by 1 i++; } // Return return ans;}// Driver Codepublic static void main(String[] args){ // Input String S = "neveropen"; int N = S.length(); System.out.println(minimumDeletion(S, N));}}// This code is contributed by Kingash |
Python3
# Python3 program for the above approachimport sys# Function to find minimum number of# character removals required to make# frequency of all distinct characters the samedef minimumDeletion(s, n): # Stores the frequency # of each character countMap = {} # Traverse the string for i in s: countMap[i] = countMap.get(i, 0) + 1 # Stores the frequency of each # character in sorted order countMultiset = [] # Traverse the Map for it in countMap: # Insert the frequency in multiset countMultiset.append(countMap[it]) # Stores the count of elements # required to be removed ans = sys.maxsize + 1 i = 0 # Stores the size of multiset m = len(countMultiset) # Traverse the multiset for j in sorted(countMultiset): # Update the ans ans = min(ans, n - (m - i) * j) # Increment i by 1 i += 1 # Return return ans# Driver Codeif __name__ == '__main__': # Input S = "neveropen" N = len(S) print (minimumDeletion(S, N))# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System.Collections.Generic; using System; class GFG{// Function to find minimum number of// character removals required to make// frequency of all distinct characters the samestatic int minimumDeletion(string s, int n){ // Stores the frequency // of each character Dictionary<char, int> countMap = new Dictionary<char, int>(); // Traverse the string for(int i = 0; i < n; i++) { if (countMap.ContainsKey(s[i]) == true) { countMap[s[i]] += 1; } else { countMap[s[i]] = 1; } } // Stores the frequency of each // character in sorted order List<int> countMultiset = new List<int>(); foreach(var values in countMap.Values) { countMultiset.Add(values); } countMultiset.Sort(); // Stores the count of elements // required to be removed int ans = 100000000; int index = 0; // Stores the size of multiset int m = countMultiset.Count; // Traverse the multiset foreach(var j in countMultiset) { // Update the ans ans = Math.Min(ans, n - (m - index) * j); // Increment i by 1 index++; } // Return return ans;}// Driver Codepublic static void Main(String[] args) { // Input string S = "neveropen"; int N = S.Length; Console.WriteLine(minimumDeletion(S, N));}}// This code is contributed by Stream_Cipher |
Javascript
<script>// JavaScript program for the above approach// Function to find minimum number of// character removals required to make// frequency of all distinct characters the samefunction minimumDeletion(s, n){ // Stores the frequency // of each character var countMap = new Map(); // Traverse the string for (var i = 0; i < n; i++) { if(countMap.has(s[i])) { countMap.set(s[i], countMap.get(s[i])+1); } else { countMap.set(s[i], 1); } } // Stores the frequency of each // character in sorted order var countMultiset = []; // Traverse the Map countMap.forEach((value, key) => { // Insert the frequency in multiset countMultiset.push(value); }); countMultiset.sort(); // Stores the count of elements // required to be removed var ans = 1000000000; var i = 0; // Stores the size of multiset var m = countMultiset.length; // Traverse the multiset countMultiset.forEach(j => { // Update the ans ans = Math.min(ans, n - (m - i) * j); // Increment i by 1 i++; }); // Return return ans;}// Driver Code// Inputvar S = "neveropen";var N = S.length;document.write( minimumDeletion(S, N));</script> |
Output:
5
Time Complexity: O(N * log(N))
Auxiliary Space: O(N) as using extra space for countMap and countMultiset
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
