#3545

Easy

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Minimum Deletions for At Most K Distinct Characters

You need to delete characters in a string to reduce its distinct characters to at most k.

hash table string greedy sorting counting

Problem Statement

You are given a string s consisting of lowercase English letters, and an integer k. Your task is to delete some characters from the string so that the resulting string contains at most k distinct characters.

Return the minimum number of deletions required to achieve this goal.

Examples

Example 1

Input: s = "abc", k = 2

Output: 1

Example 2

Input: s = "aabb", k = 2

Output: 0

Example 3

Input: s = "yyyzz", k = 1

Output: 2

Constraints

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

Solution Approach

Count character frequencies

The first step is to calculate the frequency of each character in the string. This can be done using a hash table where the keys are the characters and the values are their frequencies.

Sort frequencies

Once you have the character frequencies, sort them in increasing order. This allows us to prioritize deleting characters with lower frequencies, as removing them will minimize the number of deletions.

Greedily delete the least frequent characters

Starting from the least frequent characters, begin deleting characters until the number of distinct characters is reduced to k. The number of deletions is the number of removed characters.

Complexity Analysis

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

The time complexity depends on the sorting step, which is O(n log n) where n is the number of distinct characters in the string. The space complexity is O(n) due to the hash table used to store the character frequencies.

What Interviewers Usually Probe

Look for the candidate's ability to break the problem down into logical steps.
Assess whether they can efficiently implement frequency counting and sorting.
Evaluate their understanding of greedy algorithms and when to apply them.

Common Pitfalls or Variants

Common pitfalls

Overcomplicating the problem by attempting unnecessary operations.
Failing to handle edge cases like when the number of distinct characters is already <= k.
Incorrectly deleting characters or not updating the frequency table properly.

Follow-up variants

Consider modifying the problem to handle uppercase letters as well.
Change the deletion criteria to minimize the number of characters rather than deletions.
Allow only a fixed number of deletions, and ask how the candidate would adjust the problem to account for this constraint.

FAQ

What is the minimum number of deletions for at most k distinct characters?

The solution involves counting the frequencies of characters and deleting the least frequent characters until there are at most k distinct characters.

How do you approach the 'Minimum Deletions for At Most K Distinct Characters' problem?

Start by counting character frequencies, sorting them, and then greedily delete the least frequent characters to reduce distinct characters to k.

What is the greedy approach used in the problem?

The greedy approach is to prioritize deleting the least frequent characters first, minimizing the number of deletions required to meet the distinct character constraint.

Why do we sort the frequencies in this problem?

Sorting the frequencies allows us to easily identify the least frequent characters, which are the best candidates for deletion.

What is the time complexity of solving this problem?

The time complexity is dominated by the sorting step, which is O(n log n), where n is the number of distinct characters in the string.

terminal

Solution

Solution 1: Counting + Greedy

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

1

2

3

class Solution:
    def minDeletion(self, s: str, k: int) -> int:
        return sum(sorted(Counter(s).values())[:-k])

Continue Practicing

#3085 minimum deletions to make string k special #3081 replace question marks in string to minimize its value #3035 maximum palindromes after operations