Scale Engineer

Minimum Deletions to Make Character Frequencies Unique

Med
#1512Time: O(N), where N is the length of the string. Counting frequencies is O(N). The conflict resolution part involves iterating 26 times. The inner `while` loop's total iterations across all frequencies is bounded by the total number of deletions, which cannot exceed N. Thus, the overall complexity is dominated by the initial scan of the string.Space: O(N), where N is the length of the input string. The `occupied` boolean array can have a size up to `N+1` if a single character appears N times. The frequency count array is O(1).3 companies
Patterns
Greedy
Algorithms
Sorting
Data structures
Hash TableString
Companies
American ExpressConsultAddsmartnews

Prompt

A string s is called good if there are no two different characters in s that have the same frequency.

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

The frequency of a character in a string is the number of times it appears in the string. For example, in the string "aab", the frequency of 'a' is 2, while the frequency of 'b' is 1.

 

Example 1:

s

Example 2:

Input: s = "aaabbbcc"
Output: 2
Explanation: 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
Explanation: 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.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach first calculates the frequency of each character. Then, it iterates through these frequencies, resolving duplicates greedily. A boolean array is used to keep track of which frequency values have already been taken. When a duplicate frequency is found, it's decremented until an unused frequency value is found. The number of decrements is counted as the number of deletions.

Algorithm

  • Create an integer array charCounts of size 26 and initialize to 0.
  • Iterate through string s, incrementing charCounts[c - 'a'] for each character c.
  • Create a boolean array occupied of size s.length() + 1.
  • Initialize deletions = 0.
  • For each count in charCounts:
    • While count > 0 and occupied[count] is true:
      • Decrement count.
      • Increment deletions.
    • If count > 0, set occupied[count] to true.
  • Return deletions.

Walkthrough

  1. Count Character Frequencies: Create an integer array, say charCounts, of size 26 to store the frequency of each lowercase English letter. Iterate through the input string s and populate this array.
  2. Track Used Frequencies: Create a boolean array, occupied, of size s.length() + 1. This array will mark which frequency values are already in use by a character. occupied[f] will be true if a character has frequency f, and false otherwise.
  3. Resolve Conflicts: Initialize a variable deletions = 0. Iterate through the charCounts array. For each character's frequency freq:
    • Check if the current freq is already occupied by another character (i.e., occupied[freq] is true).
    • If it is, and freq is greater than 0, decrement freq and increment deletions. Repeat this until an unoccupied frequency is found or the frequency becomes 0.
    • If the final freq is greater than 0, mark it as occupied by setting occupied[freq] = true.
  4. Return Result: The total value of deletions is the minimum required to make the string "good".
class Solution {    public int minDeletions(String s) {        int[] charCounts = new int[26];        for (char c : s.toCharArray()) {            charCounts[c - 'a']++;        }         boolean[] occupied = new boolean[s.length() + 1];        int deletions = 0;         for (int i = 0; i < 26; i++) {            int freq = charCounts[i];            while (freq > 0 && occupied[freq]) {                freq--;                deletions++;            }            if (freq > 0) {                occupied[freq] = true;            }        }        return deletions;    }}

Complexity

Time

O(N), where N is the length of the string. Counting frequencies is O(N). The conflict resolution part involves iterating 26 times. The inner `while` loop's total iterations across all frequencies is bounded by the total number of deletions, which cannot exceed N. Thus, the overall complexity is dominated by the initial scan of the string.

Space

O(N), where N is the length of the input string. The `occupied` boolean array can have a size up to `N+1` if a single character appears N times. The frequency count array is O(1).

Trade-offs

Pros

  • Conceptually simple greedy approach.

  • Fast array lookups (occupied[freq]) provide good performance for the conflict resolution part.

Cons

  • High space complexity of O(N), which can be large if the input string is long, potentially leading to memory issues for constraints like N=10^5.

Solutions

class Solution {public  int minDeletions(String s) {    int[] cnt = new int[26];    for (int i = 0; i < s.length(); ++i) {      ++cnt[s.charAt(i) - 'a'];    }    Arrays.sort(cnt);    int ans = 0;    for (int i = 24; i >= 0; --i) {      while (cnt[i] >= cnt[i + 1] && cnt[i] > 0) {        --cnt[i];        ++ans;      }    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem