Skip to main content
Talentd

Minimum Deletions for At Most K Distinct Characters - Solution & Explanation

EasyHash TableStringGreedySorting6 min readAsked at: Meta, Google
Practice this problem

Problem Statement

You are given a string s consisting of lowercase English letters, and an integer k.

Your task is to delete some (possibly none) of the characters in the string so that the number of distinct characters in the resulting string is at most k.

Return the minimum number of deletions required to achieve this.

 

Example 1:

Input: s = "abc", k = 2

Output: 1

Explanation:

  • s has three distinct characters: 'a', 'b' and 'c', each with a frequency of 1.
  • Since we can have at most k = 2 distinct characters, remove all occurrences of any one character from the string.
  • For example, removing all occurrences of 'c' results in at most k distinct characters. Thus, the answer is 1.

Example 2:

Input: s = "aabb", k = 2

Output: 0

Explanation:

  • s has two distinct characters ('a' and 'b') with frequencies of 2 and 2, respectively.
  • Since we can have at most k = 2 distinct characters, no deletions are required. Thus, the answer is 0.

Example 3:

Input: s = "yyyzz", k = 1

Output: 2

Explanation:

  • s has two distinct characters ('y' and 'z') with frequencies of 3 and 2, respectively.
  • Since we can have at most k = 1 distinct character, remove all occurrences of any one character from the string.
  • Removing all 'z' results in at most k distinct characters. Thus, the answer is 2.

 

Constraints:

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

Approach Overview

Problem Overview: Given a string s and an integer k, delete the minimum number of characters so the resulting string contains at most k distinct characters. The key decision is which character types to remove entirely so the total deletions stay minimal.

The problem is essentially about frequency management. If the string already has <= k unique characters, no deletion is required. When there are more than k distinct characters, you must completely remove some character types. The optimal strategy keeps the characters that appear most frequently and removes the ones with the smallest counts.

Approach 1: Counting + Sorting (Greedy) (Time: O(n + m log m), Space: O(m))

Use a hash table to count the frequency of every character in the string. Let m be the number of distinct characters. If m <= k, return 0 immediately. Otherwise, collect all frequencies into a list and sort it in ascending order using a sorting algorithm. Greedily delete the least frequent characters first by summing the smallest frequencies until only k character types remain. This works because removing a rare character costs fewer deletions than removing a frequent one.

The greedy insight is straightforward: keeping high-frequency characters maximizes the remaining string length while minimizing deletions. Sorting ensures you always remove the cheapest character types first.

Approach 2: Counting + Min Heap (Greedy) (Time: O(n + m log m), Space: O(m))

Instead of sorting the entire frequency list, push all character counts into a min-heap. While the heap size is greater than k, repeatedly pop the smallest frequency and add it to the deletion count. Each pop removes one character type completely. The heap always exposes the cheapest removal candidate, which preserves the greedy property.

This approach is useful when frequencies are generated incrementally or when you want to avoid sorting the full list. The logic remains the same: eliminate the least frequent character types first.

Recommended for interviews: Counting + Sorting is the most common solution. It clearly demonstrates understanding of frequency counting with a hash map and greedy optimization. Interviewers expect you to recognize that removing entire low-frequency character groups minimizes deletions. Mentioning the heap alternative shows deeper familiarity with greedy data-structure patterns.

Solution

We can use an array cnt to count the frequency of each character. Then, we sort this array and return the sum of the first 26 - k elements.

The time complexity is O(|\Sigma| times log |\Sigma|), and the space complexity is O(|\Sigma|), where |\Sigma| is the size of the character set. In this problem, |\Sigma| = 26.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Counting + Sorting (Greedy)O(n + m log m)O(m)General solution. Simple implementation using frequency array or hash map followed by sorting.
Counting + Min HeapO(n + m log m)O(m)Useful when you want incremental greedy removal without sorting the full frequency list.
Brute Force Character RemovalO(n * m)O(m)Conceptual baseline for understanding; tries removing different character sets but inefficient for large inputs.

Video Solution

LeetCode#3545 Minimum Deletions for At Most K Distinct Characters - Python • CodeJulian • 1,656 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimum Deletions for At Most K Distinct Characters easy or hard?
The problem is generally classified as Easy because it relies on basic string traversal and frequency counting. The main insight is recognizing the greedy strategy: remove the least frequent character types first to minimize deletions.
Minimum Deletions for At Most K Distinct Characters Python/Java solution
Most implementations follow the same pattern across languages: count characters with a map or dictionary, store the frequencies, sort them, and sum the smallest frequencies until only K distinct characters remain. This approach translates directly to Python, Java, C++, Go, and TypeScript with minimal changes.
How to solve Minimum Deletions for At Most K Distinct Characters in O(n)?
First count character frequencies in O(n) using a hash table. If the number of unique characters is greater than K, sort the frequencies or use a min heap to remove the smallest frequency groups until only K remain. The counting step is O(n), and the greedy removal step adds O(m log m) where m is the number of distinct characters.
What is the best approach for Minimum Deletions for At Most K Distinct Characters?
The best approach uses frequency counting with a greedy strategy. Count each character using a hash map, sort the frequencies, and delete the smallest ones until only K distinct characters remain. This keeps high-frequency characters and minimizes deletions. The overall time complexity is O(n + m log m), where m is the number of distinct characters.
Is Minimum Deletions for At Most K Distinct Characters asked at Google/Amazon/Meta?
This pattern appears frequently in interviews at companies like Amazon, Google, and Meta because it tests string processing, frequency counting, and greedy optimization. Variations of the problem also appear in discussions about limiting distinct elements or optimizing deletions in strings.
What data structure is used in Minimum Deletions for At Most K Distinct Characters?
The core data structure is a hash table (or dictionary) to count character frequencies. After counting, a sorted list of frequencies or a min heap is used to greedily remove the least frequent characters. These structures make it efficient to track and eliminate character groups.
What is the time complexity of Minimum Deletions for At Most K Distinct Characters?
The optimal solution runs in O(n + m log m) time. O(n) is used to count character frequencies in the string, and O(m log m) is required to sort the frequency list (or operate a min heap). Space complexity is O(m) for storing character counts.

Ready to solve this problem?

Practice Minimum Deletions for At Most K Distinct Characters with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Longest Substring Without Repeating Characters