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.

← Prev Next →