Daily LeetCode Problems: Problem 1647. Minimum Deletions to Make Character Frequencies Unique

Balancing Act: Solving the Minimum Deletions Challenge

Introduction:

Welcome to another exciting problem-solving article! Today, we’ll dive into problem 1647 from LeetCode: “Minimum Deletions to Make Character Frequencies Unique”. In this challenge, we’re tasked with transforming a string into a “good” string by deleting the fewest possible characters. A string is considered “good” if no two different characters have the same frequency.

In this article, we’ll explore the problem statement, devise an efficient strategy, provide a step-by-step solution, and discuss complexity analysis.

Problem Statement:

We are given a string s, and our goal is to determine the minimum number of characters that need to be deleted to make the string "good." A "good" string is defined as one in which no two different characters have the same frequency.

For example, in the string “aab,” ‘a’ has a frequency of 2, and ‘b’ has a frequency of 1. This string is not “good” because ‘a’ appears twice.

Approach:

To solve this problem efficiently, we can use a greedy approach. We’ll iterate through the string s while keeping track of character frequencies. For each character, we'll check if its frequency is already in use. If it is, we'll increment the character's frequency until it's unique. The cost of these operations (deletions) will be added to a counter variable.

Let’s dive into the pseudocode to see how this approach works:

Pseudocode:

def minDeletions(s: str) -> int:
    # Initialize a dictionary to store character frequencies.
    freq = {}
    # Initialize a set to keep track of used frequencies.
    used_freq = set()
    # Initialize a counter for the minimum deletions.
    deletions = 0
    
    for char in s:
        # Update the character's frequency in the dictionary.
        freq[char] = freq.get(char, 0) + 1
        # Keep incrementing the frequency until it's unique.
        while freq[char] in used_freq:
            freq[char] -= 1
            deletions += 1
        # Add the current frequency to the used set.
        used_freq.add(freq[char])
    
    return deletions

Complexity Analysis:

Let’s analyze the complexity of our solution:

• Time complexity: We iterate through the string s once, which takes O(n) time, where n is the length of the string.
• Space complexity: We use two data structures, freq and used_freq, which can each store up to O(n) unique characters. Therefore, the space complexity is O(n).

Step-by-Step Solution:

1. Initialize an empty dictionary freq to store character frequencies, an empty set used_freq to keep track of used frequencies, and a variable deletions to count the minimum deletions.
2. Iterate through each character char in the string s.
3. Update the frequency of the current character in the freq dictionary. We use the get method with a default value of 0 to handle characters not yet encountered.
4. Check if the current character’s frequency is already in the used_freq set. If it is, we have a conflict.
5. If there’s a conflict, decrement the character’s frequency until it’s unique. For each decrement, increment the deletions counter.
6. Add the current character’s frequency to the used_freq set.
7. Continue this process for each character in the string.
8. After processing all characters, return the deletions count as the minimum number of deletions required to make the string "good."

Full Solution

Python

class Solution:
  def minDeletions(self, s: str) -> int:
    ans = 0
    count = collections.Counter(s)
    usedFreq = set()

    for freq in count.values():
      while freq > 0 and freq in usedFreq:
        freq -= 1  # Delete ('a' + i).
        ans += 1
      usedFreq.add(freq)

    return ans

Java

class Solution {
  public int minDeletions(String s) {
    int ans = 0;
    int[] count = new int[26];
    Set<Integer> usedFreq = new HashSet<>();

    for (final char c : s.toCharArray())
      ++count[c - 'a'];

    for (int freq : count) {
      while (freq > 0 && usedFreq.contains(freq)) {
        --freq; // Delete ('a' + i).
        ++ans;
      }
      usedFreq.add(freq);
    }

    return ans;
  }
}

C++

class Solution:
  def minDeletions(self, s: str) -> int:
    ans = 0
    count = collections.Counter(s)
    usedFreq = set()

    for freq in count.values():
      while freq > 0 and freq in usedFreq:
        freq -= 1  # Delete ('a' + i).
        ans += 1
      usedFreq.add(freq)

    return ans

Conclusion:

In this article, we tackled problem 1647, “Minimum Deletions to Make Character Frequencies Unique,” by using a greedy approach to minimize the number of deletions required to transform a string into a “good” string. Understanding the problem statement and implementing our approach will enable you to efficiently solve similar challenges that involve string manipulation and frequency analysis. Happy coding!