Minimum number of characters required to be removed such that every character occurs same number of times

0 0 5 minutes read

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 = “zambiatek”
Output : 5
Explanation: Removing an occurrence of ‘r’, ‘f’, ‘and ‘o’ and removing two occurrences of ‘e’ modifies S to “zambiatekgks”.

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 same
int 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 Code
int main()
{
    // Input
    string S = "zambiatek";
    int N = S.length();
 
    cout << minimumDeletion(S, N);
 
    return 0;
}

Java

// Java program for the above approach
import 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 same
static 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 Code
public static void main(String[] args)
{
    // Input
    String S = "zambiatek";
    int N = S.length();
 
    System.out.println(minimumDeletion(S, N));
}
}
 
// This code is contributed by Kingash

Python3

# Python3 program for the above approach
import sys
 
# Function to find minimum number of
# character removals required to make
# frequency of all distinct characters the same
def 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 Code
if __name__ == '__main__':
     
    # Input
    S = "zambiatek"
    N = len(S)
 
    print (minimumDeletion(S, N))
 
# This code is contributed by mohit kumar 29

C#

// C# program for the above approach
using System.Collections.Generic; 
using System; 
 
class GFG{
 
// Function to find minimum number of
// character removals required to make
// frequency of all distinct characters the same
static 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 Code
public static void Main(String[] args) 
{ 
     
    // Input
    string S = "zambiatek";
    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 same
function 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
// Input
var S = "zambiatek";
var N = S.length;
document.write( minimumDeletion(S, N));
 
</script>

Output:

Time Complexity: O(N * log(N))
Auxiliary Space: O(N) as using extra space for countMap and countMultiset

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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 zambiatek!