Problem Description

I assume you have read the original problem description in the link above, so I will share some key points about a common mistake in the problem, which is using a greedy approach.

A common mistake: greedily delete from the most common characters

1. Get the frequency of characters in a word
2. Rank the frequency of characters by their occurrence (head=most frequent, tail=least frequent)
3. if the maximum difference between head to tail is more than k, delete the character in the head (max difference-1) until their difference is smaller than K

   class Solution:
    def minimumDeletions(self, word: str, k: int) -> int:
        # 1. get the frequency of characters in word
        # 2. rank the frequency of characters by their occurance (head=most frequent, tail=least frequent)
        # 3. if the maxium difference between head to tail is more than k, delete character in head (max difference-1) until their difference is smaller than K
        counter = Counter(word)
        ranked = counter.most_common()
        head = 0
        tail = len(ranked) - 1
        res = 0
        head_tail_difference = ranked[head][1] - ranked[tail][1]
        while (head_tail_difference > k):
            res += 1
            counter[ranked[head][0]] -= 1
            if counter[ranked[head][0]] == 0:
                del counter[ranked[head][0]]  # Remove completely
            ranked = counter.most_common()
            tail = len(ranked) - 1
            head_tail_difference = ranked[head][1] - ranked[tail][1]
        return res
   

When testing on word ="aabcaba", k=0, this approach gives a wrong answer of 4.

• rank [('a', 3), ('b', 2), ('c', 1)] del a res 1
• rank [('a', 2), ('b', 2), ('c', 1)] del a res 2
• rank [('b', 2), ('a', 1), ('c', 1)] del b res 3
• rank [('a', 1), ('b', 1), ('c', 1)] del a res 4

But the right way is to:

• rank [('a', 3), ('b', 2), ('c', 1)] del a res 1
• rank [('a', 2), ('b', 2), ('c', 1)] del a res 2
• rank [('a', 2), ('b', 2)] del c res 3

Why doesn't it work?

Besides the test example, there is another simple example to understand why greedy approach can't guarantee the optimal solution.

Let's say we have frequency {'a':3, 'b':4, 'c':1} and k = 0.

Will you decrease from 'a' and 'b', or will you delete 'c' if you want to use the least effort to make them equal? You will decrease from 'c', right?

Another example is if we have equal occurrences like {'a': 3, 'b': 3, 'c': 1}, how do you decide which character to delete?

How to fix it? Add the minimum into consideration

In order to fix it, we need to take the minimum into consideration. To be specific, what's the minimum and maximum number we can have if we want to put the number in our final list?

Let's use the idea to run the test on word ="aabcaba", k=0 again. The rank is [('a', 4), ('b', 2), ('c', 1)]

For 'a', since the occurrence is 4, if we put it into our list, we can't put 'b' and 'c' into the list. So the times of deletion are 3.

For 'b', since the occurrence is 2, if we put into our list, we can't have 'a' or 'c'. So the times of deletion are 5.

For 'c', if we want to put into our list, we can't have 'a' or 'b'. So the times of deletion are 6.

After comparison, we find that put 'a' in is the optimal solution.

Core strategy(step by step explained):

1. Setup

   counter = Counter(word)           # Count frequency of each character
   frequencies = sorted(counter.values())  # Get sorted list of frequencies
   min_deletions = float('inf')      # Track minimum deletions found
   

2. Try Every Range For each possible minimum frequency, we define a valid range [target_min, target_max] where target_max - target_min = k.

   for target_min in frequencies:   # Try each frequency as the minimum
    target_max = target_min + k   # Maximum allowed = minimum + k
   

3. Calculate Deletions for Current Range

   for freq in frequencies:
    if freq < target_min:
        deletions += freq              # Delete entire character (too low)
    elif freq > target_max:
        deletions += freq - target_max # Reduce to maximum allowed (too high)
    # If target_min ≤ freq ≤ target_max: no deletions needed
   

4. Track the Best Solution

   min_deletions = min(min_deletions, deletions)
   

   Complexity analysis

   1. Time complexity: O(n^2)

   Let's break it down:

5. Counter creation: Counter(word) → O(n) where n = length of word

6. Sorting frequencies: sorted(counter.values()) → O(m log m) where m = number of unique characters
7. Nested loops:
   • Outer loop: iterates through each unique frequency → O(m)
   • Inner loop: iterates through all frequencies again → O(m)
   • Combined: O(m²)
8. Overall: O(n + m log m + m²)
9. Since m ≤ n (unique characters can't exceed total characters), and in the worst case m = n (all characters unique), the dominant term is O(m²) = O(n²).

2. Space complexity: O(n)

• Counter storage: O(m) for storing frequency of each unique character
• Frequencies list: O(m) for storing sorted frequencies

• Other variables: O(1) for counters and temporary variables

• Total: O(m) where m = number of unique characters

• In practice:
  • Best case: m = 1 (all same character) → O(n) time, O(1) space
  • Worst case: m = n (all different characters) → O(n²) time, O(n) space
  • Typical case: m is much smaller than n → closer to O(n) time

Dry run

word = "aaabbbc", k = 1 frequencies = [1, 3, 3] # sorted

Try target_min = 1: range [1, 2]

• freq=1: 1 ∈ [1,2] → 0 deletions
• freq=3: 3 > 2 → delete 1 → 1 deletion
• freq=3: 3 > 2 → delete 1 → 1 deletion Total: 2 deletions

Try target_min = 3: range [3, 4]

• freq=1: 1 < 3 → delete all → 1 deletion
• freq=3: 3 ∈ [3,4] → 0 deletions
• freq=3: 3 ∈ [3,4] → 0 deletions
  Total: 1 deletion ← minimum!

Full solution

class Solution:
    def minimumDeletions(self, word: str, k: int) -> int:
        counter = Counter(word)
        frequencies = sorted(counter.values())
        min_deletions = float('inf')

        # Try each possible minimum frequency as target
        for target_min in frequencies:
            target_max = target_min + k
            deletions = 0

            for freq in frequencies:
                if freq < target_min:
                    deletions += freq  # Delete entire character
                elif freq > target_max:
                    deletions += freq - target_max  # Reduce to max allowed

            min_deletions = min(min_deletions, deletions)

        return min_deletions