Minimum Deletions for At Most K Distinct Characters

Difficulty: Easy | Acceptance: 73.10% | Paid: No Topics: Hash Table, String, Greedy, Sorting, Counting

Given a string s and an integer k, return the minimum number of characters you need to delete from s so that the resulting string contains at most k distinct characters.

• Examples
• Constraints
• Sorting (Greedy)
• Bucket Sort (Counting)

Examples

Input: s = "aabab", k = 2
Output: 0
Explanation: The string already has at most 2 distinct characters ('a' and 'b').

Input: s = "aabab", k = 1
Output: 2
Explanation: We can delete the two 'b's to get "aaa".

Input: s = "abc", k = 2
Output: 1
Explanation: We can delete 'c' to get "ab".

Constraints

- 1 <= s.length <= 16
- 1 <= k <= 16
- s consists only of lowercase English letters.

Sorting (Greedy)

Intuition To minimize deletions, we should maximize the length of the string we keep. Since we are limited to keeping at most k distinct characters, we should keep the k characters that appear most frequently in the original string.

Steps

• Count the frequency of each character in the string.
• Store these frequencies in a list.
• Sort the list of frequencies in descending order.
• Sum the first k frequencies (or all of them if there are fewer than k distinct characters). This sum represents the maximum length of the string we can keep.
• Subtract this sum from the total length of the string to get the number of deletions.

class Solution:\n    def minimumDeletions(self, s: str, k: int) -> int:\n        from collections import Counter\n        \n        # Count frequency of each character\n        freq_map = Counter(s)\n        \n        # Extract frequencies and sort them in descending order\n        frequencies = list(freq_map.values())\n        frequencies.sort(reverse=True)\n        \n        # Sum the top k frequencies\n        keep = 0\n        for i in range(min(k, len(frequencies))):\n            keep += frequencies[i]\n            \n        # Deletions = total length - length we keep\n        return len(s) - keep\n

Complexity

• Time: O(N + M log M), where N is the length of the string and M is the number of distinct characters (at most 26). Since M is constant, this is effectively O(N).
• Space: O(M) to store the frequency map and list.
• Notes: Sorting is very efficient here because the number of distinct characters is capped at 26.

Bucket Sort (Counting)

Intuition Since the input consists only of lowercase English letters, the number of distinct characters is small (26). However, the frequency of a character can be up to 10⁵. Instead of sorting the frequencies, we can use a “Bucket Sort” approach where we iterate through possible frequencies from high to low to greedily pick the most frequent characters.

Steps

• Count the frequency of each character using a fixed-size array of length 26.
• Determine the maximum frequency present in the string.
• Create a bucket array of size max_freq + 1, where bucket[i] stores the count of distinct characters that have a frequency of i.
• Iterate from max_freq down to 0. For each frequency i, if we still need characters (i.e., k > 0), we take characters from this bucket.
• The total length kept is the sum of i * count_taken for each bucket.
• Return len(s) - total_kept.

class Solution:\n    def minimumDeletions(self, s: str, k: int) -> int:\n        # Count frequencies using a fixed array (26 lowercase letters)\n        count = [0] * 26\n        for char in s:\n            count[ord(char) - ord(\'a\')] += 1\n            \n        # Filter out zero frequencies\n        frequencies = [f for f in count if f > 0]\n        \n        # Find max frequency to size the bucket array\n        max_freq = max(frequencies) if frequencies else 0\n        \n        # Bucket sort: bucket[i] = number of chars with frequency i\n        bucket = [0] * (max_freq + 1)\n        for f in frequencies:\n            bucket[f] += 1\n            \n        # Greedily pick top k frequencies\n        keep = 0\n        chars_remaining = k\n        \n        for i in range(max_freq, -1, -1):\n            if bucket[i] == 0:\n                continue\n            \n            # We can take at most bucket[i] chars from this frequency level\n            take = min(bucket[i], chars_remaining)\n            keep += take * i\n            chars_remaining -= take\n            \n            if chars_remaining == 0:\n                break\n                \n        return len(s) - keep\n

Complexity

• Time: O(N + M), where N is the length of the string and M is the maximum frequency of any character. Since M can be up to N, this is O(N).
• Space: O(M) for the bucket array.
• Notes: This approach avoids the logarithmic factor of sorting by iterating through the frequency range. It is particularly efficient if the frequency range is not significantly larger than the number of distinct characters.