# Minimum Character Deletion Problem in Java

The Minimum Character Deletion Problem determines the number of characters that must be removed from a string to ensure that each character's frequency is unique.

Example 1

Input: “abbabc”

Output: Minimum Character Deletions: 0

Explanation: Both “a” and “b” have 2 occurrences. Deleting one “b” makes all frequencies unique.

Example 2

Input: “aabbccc”

Output: Minimum Character Deletions: 1

Explanation: We must delete one "a" and one "b" to achieve unique frequencies.

Example 3

Input: “ceabaacb”

Output: Minimum Character Deletions: 2

Explanation: Each character needs to be reduced to one occurrence.

## Approach 1: Using HashMap

The minimum Character Deletion problem enables efficient frequency counting of characters in the input string using the HashMap. HashMap dynamically resizes to accommodate varying string lengths, and their constant-time lookup ensures quick access to character frequencies.

### Algorithm

Step 1: Create a HashMap to store the frequency of each character in the string.

Step 2: Create an array freqCount to store the frequency of frequencies.

Step 3:  Iterate from the highest frequency to the lowest.

Step 4: If a frequency appears more than once, perform deletions:

Step 4.1: Calculate the number of characters to delete to make the frequency unique.

Step 4.2: Shift frequencies to the left in the freqCount Array.

Step 5: Return the deletions variable, which stores the deleted characters.

Filename: MinimumCharacterDeletionUsingHashMap.java

`import java.util.HashMap;import java.util.Map;public class MinimumCharacterDeletionUsingHashMap {    public static int minDeletions(String str) {        // Frequency map to store the count of each character        Map<Character, Integer> freqMap = new HashMap<>();        // Populate the frequency map        for (char c : str.toCharArray()) {            freqMap.put(c, freqMap.getOrDefault(c, 0) + 1);        }        int deletions = 0;        // Set to keep track of frequencies encountered so far        Map<Integer, Boolean> freqSet = new HashMap<>();        // Iterate over the frequency map        for (int freq : freqMap.values()) {            // If the current frequency is already present in the set, increment deletions            while (freqSet.containsKey(freq)) {                deletions++;                freq--; // Reduce the frequency to make it unique            }            // Add the frequency to the set            freqSet.put(freq, true);        }        return deletions;    }    public static void main(String[] args) {        String str = "ceabaacb";        int minDeletions = minDeletions(str);        System.out.println("Minimum deletions required: " + minDeletions);    }}`

Output:

`Minimum deletions required: 2`

Time Complexity: The time complexity is O(n). This is because the code iterates through the string once to calculate the frequency of each character and then iterates through the frequency count array to determine the deletions needed to make each frequency unique.

Space Complexity: The space complexity is O(n). The Array stores the frequency of frequencies, which can range from 0 to the length of the string.

## Approach 2: Using PriorityQueue

The Minimum Character Deletion Problem in Java can be solved by using PriorityQueue.

### Algorithm

Step 1: Count the frequency of each character in the input string using a HashMap.

Step 2: Create a PriorityQueue to store the frequencies in descending order.

Step3: Iterate through the PriorityQueue:

Step 3.1: If the current frequency is the same as the previous one and there is more than one occurrence, increment the deletion count.

Step 3.2: Otherwise, update the previous frequency.

Step 4: If the frequency is still more than one, reduce it by one and add it back to the PriorityQueue.

Step 5: Return the total number of deletions.

Filename: MinimumCharacterDeletionUsingPriorityQueue.java

`import java.util.*;public class MinimumCharacterDeletionUsingPriorityQueue {    public static int minDeletionsToMakeFreqUnique(String s) {        // Frequency counts of characters in the string        Map<Character, Integer> freqMap = new HashMap<>();        // Populate frequency map        for (char c : s.toCharArray()) {            freqMap.put(c, freqMap.getOrDefault(c, 0) + 1);        }        // Priority queue to store frequencies        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());        pq.addAll(freqMap.values());        int deletions = 0;        // Calculate the deletions required        while (!pq.isEmpty()) {            int freq = pq.poll();            if (!pq.isEmpty() && freq == pq.peek()) {                deletions++;                if (freq > 1) {                    pq.offer(freq - 1);                }            }        }        return deletions;    }    public static void main(String[] args) {        String s = "aabbccc";        int minDeletions = minDeletionsToMakeFreqUnique(s);        System.out.println("Minimum number of characters to be deleted: " + minDeletions);    }}`

Output

`Minimum number of characters to be deleted: 1`

Time Complexity: The program's time complexity is O(n log n), where n is the length of the input string. The priority queue iterates each character once and performs priority queue operations.

Space Complexity: The program's space complexity is O(n), where n is the length of the input. The space required for the HashMap is proportional to the number of distinct characters in the input string. The priority queue stores the frequencies, which contributes to the space complexity.