medium Minimum Deletions to Make Character Frequencies Unique

Problem Statement

Given a string str, return the minimum number of characters you need to delete to make str good.

A good string doesn't contain two different characters with the same frequency.

Examples

Example 1:

• Input: "aabbbb"
• Expected Output: 0
• Justification: In the given string, the frequency of a is 2, and the frequency of b is 4. Each character already has a unique frequency. So, no need to delete any character from the string

Example 2:

• Input: "aaaabbbbcc"
• Expected Output: 1
• Justification: The character 'c' appears twice, and 'a' and 'b' appear four times each. To make all frequencies unique, we can delete one occurrence of either 'a' or 'b'. This leaves us with 'a', 'b', and 'c' having frequencies of 3, 4, and 2, respectively.

Example 3:

• Input: "aabbcc"
• Expected Output: 3
• Justification: Here, each character's frequncey is 2. By deleting both a and 1 b, we can make frequency unique.

Solution

To solve this problem, we can adopt a strategy that focuses on counting the frequency of each character in the string and then adjusting those frequencies to ensure uniqueness. The initial step involves creating a frequency count for each character. Once we have this frequency map, we'll sort these frequencies in descending order. This allows us to iteratively adjust the higher frequencies to make them unique, minimizing the total number of deletions required. This approach works because by starting from the highest frequencies, we ensure that any necessary adjustments result in the minimal possible change, thereby preserving as much of the original string as possible.

This method is effective because it directly addresses the requirement for uniqueness in character frequencies by systematically reducing frequencies from the highest down, ensuring that each adjustment contributes to the goal with the minimal number of deletions. By doing so, it avoids unnecessary deletions and efficiently achieves the target state with optimal moves.

Step-by-step algorithm

1. Count Frequencies: First, count the frequency of each character in the string.
2. Sort Frequencies: Sort these frequencies in descending order.
3. Adjust Frequencies: Initialize a variable to keep track of the total deletions. For each frequency starting from the second highest, do the following:
   • If the current frequency is equal to or greater than the previous frequency, decrease it to one less than the previous frequency (if the previous frequency is greater than 0).
   • Increase the total deletions count by the number of deletions made to adjust the current frequency.
   • Update the previous frequency to the current (adjusted) frequency.
4. Return Total Deletions: The total deletions variable now contains the minimum number of deletions required to ensure all character frequencies are unique.

Algorithm Walkthrough

Let's consider the Input: "aaaabbbbcc"

1. Count Frequencies:

   • Count the frequency of each character in the string.
   • Frequencies: {'a': 4, 'b': 4, 'c': 2}

2. Sort Frequencies:

   • Sort the frequencies in descending order to address the highest frequencies first, which gives us [4, 4, 2].

3. Adjust Frequencies:

   • Start with the second highest frequency (since the first one does not have a preceding frequency to compare with) and make adjustments to ensure each frequency is unique.

   First Iteration (Second '4'):

   • The first '4' (for 'a') has no conflict and remains unchanged.
   • The second '4' (for 'b') is equal to the first '4'. To make it unique, we need to reduce it to the frequency[i - 1] - 1 = frequency[0] - 1 = 4 - 1 = 3. .
   • Action: Reduce the second '4' to '3'.
   • Deletions: 1 (from 'b').
   • Frequencies now: [4 (a's frequency, unchanged), 3 (adjusted b's frequency), 2 (c's unchanged frequency)].

   No Further Adjustments Needed:

   • The next frequency is '2' (for 'c'), which is already unique in the context of the adjusted frequencies.
   • No adjustment or deletion is required for 'c'.

4. Total Deletions:

   • The total deletions required to make the frequencies unique are 1 (one deletion from 'b').

Code

import java.util.*;

public class Solution {

  // Method to calculate the minimum deletions required to make character frequencies unique
  public int minDeletions(String s) {
    Map<Character, Integer> frequencyMap = new HashMap<>();
    // Counting the frequency of each character in the string
    for (char c : s.toCharArray()) {
      frequencyMap.put(c, frequencyMap.getOrDefault(c, 0) + 1);
    }

    List<Integer> frequencies = new ArrayList<>(frequencyMap.values());
    Collections.sort(frequencies, Collections.reverseOrder()); // Sorting frequencies in descending order

    int deletions = 0;
    for (int i = 1; i < frequencies.size(); i++) {
      if (frequencies.get(i) >= frequencies.get(i - 1)) {
        int desiredFrequency = Math.max(0, frequencies.get(i - 1) - 1); // Calculating the desired frequency to make it unique
        deletions += frequencies.get(i) - desiredFrequency; // Calculating deletions needed
        frequencies.set(i, desiredFrequency); // Updating the frequency to the adjusted (unique) frequency
      }
    }

    return deletions; // Returning the total deletions required
  }

  public static void main(String[] args) {
    Solution solution = new Solution();
    // Testing the algorithm with the provided examples
    System.out.println(solution.minDeletions("aabbbb")); // Example 1: Expected Output: 0
    System.out.println(solution.minDeletions("aaaabbbbcc")); // Example 2: Expected Output: 1
    System.out.println(solution.minDeletions("aabbcc")); // Example 3: Expected Output: 3
  }
}

Complexity Analysis:

Time Complexity

• The time complexity is , where (n) is the length of the string and (k) is the number of unique characters in the string.
• Counting frequencies takes time.
• Sorting the frequencies takes time, where (k) is the number of unique characters.
• The loop to adjust frequencies and calculate deletions takes time.

Space Complexity

The space complexity is , where (k) is the number of unique characters in the string. This is due to the additional storage needed for the frequency map and the list of frequencies.