#1647

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Minimum Deletions to Make Character Frequencies Unique

Determine the minimum deletions needed to ensure all character frequencies in a string are unique using a greedy approach.

hash table string greedy sorting

Problem Statement

Given a string s consisting of lowercase English letters, define it as 'good' if no two distinct characters share the same frequency. Frequencies are determined by counting how many times each character appears in s.

Return the minimum number of character deletions required to transform s into a good string. For instance, if multiple characters have the same frequency, selectively reduce their counts until all frequencies are unique, ignoring characters with zero frequency.

Examples

Example 1

Input: s = "aab"

Output: 0

s is already good.

Example 2

Input: s = "aaabbbcc"

Output: 2

You can delete two 'b's resulting in the good string "aaabcc". Another way it to delete one 'b' and one 'c' resulting in the good string "aaabbc".

Example 3

Input: s = "ceabaacb"

Output: 2

You can delete both 'c's resulting in the good string "eabaab". Note that we only care about characters that are still in the string at the end (i.e. frequency of 0 is ignored).

Constraints

1 <= s.length <= 105
s contains only lowercase English letters.

Solution Approach

Count character frequencies

Use a hash table to tally the occurrence of each character in the string. This provides a mapping from characters to counts, forming the basis for identifying duplicates in frequency.

Apply greedy frequency reduction

Iterate over the character frequencies. For each frequency, if it has already been used, decrement it until either zero or an unused frequency is found, incrementing the deletion counter each step. This directly implements the greedy choice plus invariant validation pattern.

Return total deletions

Sum all decrements made during the frequency adjustment process. This total represents the minimal deletions needed to ensure all remaining character frequencies are unique.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) to count frequencies plus O(k log k) if sorting frequencies is used, where k is the number of distinct characters; space complexity is O(k) for the frequency map and O(k) for the set of used frequencies.

What Interviewers Usually Probe

Expect a linear scan over the frequency counts with conflict resolution.
Watch for edge cases where multiple characters share the same frequency.
Check that zero-frequency characters are ignored when validating uniqueness.

Common Pitfalls or Variants

Common pitfalls

Failing to decrement frequencies correctly when duplicates exist, leading to overcounted deletions.
Not ignoring characters reduced to zero frequency, which can falsely appear as conflicts.
Assuming characters must be deleted in input order rather than using a frequency-based greedy reduction.

Follow-up variants

Find the minimum insertions to make all character frequencies unique instead of deletions.
Apply the same frequency uniqueness constraint to subsets of the string or sliding windows.
Modify the problem to allow only specific characters to be deleted, testing selective greedy application.

FAQ

What is the main pattern to recognize in Minimum Deletions to Make Character Frequencies Unique?

The key pattern is greedy choice plus invariant validation: always reduce the highest conflicting frequency to achieve uniqueness efficiently.

Can this problem be solved without sorting the frequencies?

Yes, you can use a set to track used frequencies and decrement conflicting frequencies iteratively, avoiding explicit sorting.

Why are characters with zero frequency ignored?

Once a character's frequency reaches zero, it effectively no longer exists in the string, so it doesn't count toward frequency conflicts.

What data structure is best for counting frequencies?

A hash table or dictionary mapping characters to counts is optimal, allowing O(1) updates and lookups for each character.

How does GhostInterview prevent common pitfalls in this problem?

It tracks used frequencies and guides frequency reduction decisions, ensuring minimal deletions and correct handling of zero-frequency cases.

terminal

Solution

Solution 1: Array + Sorting

First, we use an array $\textit{cnt}$ of length $26$ to count the occurrences of each letter in the string $s$.

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def minDeletions(self, s: str) -> int:
        cnt = Counter(s)
        ans, pre = 0, inf
        for v in sorted(cnt.values(), reverse=True):
            if pre == 0:
                ans += v
            elif v >= pre:
                ans += v - pre + 1
                pre -= 1
            else:
                pre = v
        return ans

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def minDeletions(self, s: str) -> int:
        cnt = Counter(s)
        ans, pre = 0, inf
        for v in sorted(cnt.values(), reverse=True):
            if pre == 0:
                ans += v
            elif v >= pre:
                ans += v - pre + 1
                pre -= 1
            else:
                pre = v
        return ans

Continue Practicing

#767 reorganize string #1657 determine if two strings are close #1604 alert using same key card three or more times in a one hour period