We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Deletions to Make Character Frequencies Unique

Difficulty: Medium

Problem Description

Given a string s, return the minimum number of characters you need to delete to make s good, where a string is called good if there are no two different characters that have the same frequency.

Key Insights

  • A character's frequency is the number of times it appears in the string.
  • To make the string good, we need to ensure that all character frequencies are unique.
  • We can achieve this by keeping track of the frequencies and adjusting them to avoid duplicates.

Space and Time Complexity

Time Complexity: O(n + k log k), where n is the length of the string and k is the number of unique characters. The sorting step contributes to the log factor. Space Complexity: O(k), where k is the number of unique characters for the frequency map.

Solution

To solve the problem, we can follow these steps:

  1. Count the frequency of each character in the string using a hash table (dictionary).
  2. Store the frequencies in a list and sort it in descending order.
  3. Iterate through the sorted list and check for duplicates. If a frequency is found that is not unique, reduce it until it becomes unique, counting the number of deletions required.
  4. Return the total number of deletions.

This approach ensures that we efficiently manage the character frequencies and maintain uniqueness.

Code Solutions

from collections import Counter

def minDeletions(s: str) -> int:
    freq = Counter(s)  # Count frequency of each character
    freq_values = sorted(freq.values(), reverse=True)  # Sort frequencies in descending order
    deletions = 0
    seen = set()  # To track seen frequencies

    for f in freq_values:
        # Ensure f is unique
        while f in seen and f > 0:
            f -= 1  # Decrease frequency
            deletions += 1  # Count deletion
        seen.add(f)  # Add the unique frequency to the set

    return deletions
← Back to All Questions