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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Deletions to Make Character Frequencies Unique

Number: 1770

Difficulty: Medium

Paid? No

Companies: Amazon, Microsoft, American Express

Problem Description

Given a string s, a string is called good if no two distinct characters have the same frequency. The goal is to find the minimum number of deletions required from s so that it becomes good.

Key Insights

  • Count the frequency of each character in the string.
  • Use a greedy approach to ensure that each frequency is unique.
  • Utilize a set (or similar data structure) to keep track of frequencies already used.
  • For each character’s frequency, if it conflicts with an already used frequency, reduce the frequency (simulate deletion) until it becomes unique or zero.
  • The problem leverages sorting or iterating over a small fixed alphabet (26 letters) for efficiency.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the string (plus a negligible factor for iterating over at most 26 unique characters).
Space Complexity: O(1) since the frequency dictionary and set have at most 26 keys.

Solution

The solution begins by counting the frequency of every character in the string. Then, iterate over these frequencies and use a set to check for uniqueness. If a frequency already exists in the set, decrement the frequency (and count a deletion) until you either find a unique frequency or drop to 0. This greedy adjustment minimizes the total number of deletions required. The main data structures used are a hash map (or dictionary) for frequency counting and a set to track used frequencies.

Code Solutions

def minDeletions(s: str) -> int:
    # Count the frequency of each character in the string.
    from collections import Counter
    freq_counter = Counter(s)
    
    # Initialize a set to track frequencies that have been used.
    used_frequencies = set()
    deletions = 0
    
    # Iterate over each character's frequency.
    for char, freq in freq_counter.items():
        # Adjust the frequency until it becomes unique (or zero)
        while freq > 0 and freq in used_frequencies:
            freq -= 1  # simulate deletion of a character
            deletions += 1
        # Add the (now unique) frequency to the set if it is positive.
        used_frequencies.add(freq)
    
    return deletions

# Example usage:
print(minDeletions("aaabbbcc"))  # Output: 2
← Back to All Questions