Minimum Deletions for At Most K Distinct Characters

Easy

Asked by:

20 views

Topics:

StringsGreedy Algorithms

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.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of possible values for `k`, and what happens if `k` is zero?
Can the input string be empty or null? If so, what should the function return?
Are we only concerned with ASCII characters, or should I consider Unicode characters in the input string?
If there are multiple solutions resulting in the same minimum number of deletions, is any valid solution acceptable, or is there a tie-breaker?
Is the input string case-sensitive? Should 'A' and 'a' be considered distinct characters?

Brute Force Solution

Approach

The brute force strategy explores every possible combination of deletions to find the smallest number that results in at most K unique characters. It works by systematically removing characters and checking the remaining string.

Here's how the algorithm would work step-by-step:

Start with the original string.
Consider deleting zero characters. How many unique characters are there? If it is less than or equal to K, you have a potential solution.
Now, consider deleting one character. Try deleting each character in the string individually. For each deletion, count the number of unique characters. If the number is less than or equal to K, note down the number of deletions as a possible solution.
Next, consider deleting two characters. Try every possible pair of characters to delete from the original string. For each pair deletion, count the unique characters. If it is less than or equal to K, record the number of deletions.
Continue this process, incrementing the number of characters to delete each time.
Repeat until you have considered deleting all possible combinations of characters.
From all the solutions where the number of unique characters is less than or equal to K, choose the one with the minimum number of deletions. This is your answer.

Code Implementation

def minimum_deletions_brute_force(input_string, max_distinct):
    string_length = len(input_string)
    minimum_deletions = string_length + 1

    for i in range(1 << string_length):
        number_of_deletions = 0
        current_string = ""

        for j in range(string_length):
            if (i >> j) & 1:
                number_of_deletions += 1
            else:
                current_string += input_string[j]

        # Ensure we process only valid string combinations

        unique_characters = len(set(current_string))

        if unique_characters <= max_distinct:
            minimum_deletions = min(minimum_deletions, number_of_deletions)

    if minimum_deletions == string_length + 1:
        return -1

    # Return the calculated minimum deletions
    return minimum_deletions

Big(O) Analysis

Time Complexity

O(2^n) – The algorithm explores all possible combinations of character deletions from the string. For a string of length n, there are 2^n possible subsets (each character can either be deleted or not). For each subset, the algorithm needs to count the number of unique characters in the remaining string, which takes O(n) time in the worst case. Therefore, the overall time complexity is O(n * 2^n), which simplifies to O(2^n) since the exponential term dominates. The algorithm checks character counts for all combinations leading to the exponential runtime.

Space Complexity

O(N) – The brute force solution involves generating all possible combinations of deletions. To count the unique characters for each deletion combination, a temporary data structure (e.g., a string or a character array) of size at most N (the length of the original string) is needed. Additionally, a set or a frequency map of characters might be used within each such combination to count the unique characters, and its size can be up to N in the worst case where all characters are unique. Therefore, the auxiliary space complexity is O(N).

Optimal Solution

Approach

The goal is to remove the fewest letters possible from a string so that it contains at most a certain number of unique characters. We can achieve this by carefully tracking how many times each letter appears and strategically removing letters from the least frequent ones.

Here's how the algorithm would work step-by-step:

First, count how many times each letter appears in the string.
Then, keep track of how many distinct letters are currently present.
If the number of distinct letters is already at or below the allowed limit, then no letters need to be removed.
Otherwise, repeatedly remove the least frequent letter until the number of distinct letters is at or below the allowed limit.
To figure out which is the least frequent letter, consider all the letters that have appeared, and remove the one with the smallest count.
Keep a running total of how many letters you have removed, and this is the answer.

Code Implementation

def min_deletions(input_string, max_distinct_characters):
    character_counts = {}
    for char in input_string:
        character_counts[char] = character_counts.get(char, 0) + 1

    distinct_characters_count = len(character_counts)

    # No deletions are needed if we already have <= K distinct chars
    if distinct_characters_count <= max_distinct_characters:
        return 0

    number_of_letters_removed = 0

    while distinct_characters_count > max_distinct_characters:

        # Find the least frequent character to remove.
        least_frequent_character = None
        min_count = float('inf')
        for char, count in character_counts.items():
            if count < min_count:
                min_count = count
                least_frequent_character = char

        # Remove the least frequent character from consideration.
        number_of_letters_removed += character_counts[least_frequent_character]
        del character_counts[least_frequent_character]

        # Removing a character reduces distinct character count
        distinct_characters_count -= 1

    return number_of_letters_removed

Big(O) Analysis

Time Complexity

O(n log n) – Counting the frequency of each character takes O(n) time where n is the length of the string. Determining the distinct characters also takes O(n). Then, in the worst case, we might have to remove characters until only k distinct characters remain. To efficiently find the least frequent character repeatedly, we can use a min-heap (priority queue) which can be constructed in O(n) time. Each deletion from the min-heap takes O(log n) time, and in the worst case, we might perform n deletions. Therefore, the overall time complexity is dominated by the heap operations, which takes O(n log n) in the worst-case.

Space Complexity

O(1) – The algorithm primarily uses a frequency map to store the count of each letter and a few variables to keep track of the number of distinct characters and the number of deletions. The frequency map's size is bounded by the size of the alphabet, which is considered constant. The number of extra variables needed does not depend on the input string's length (N), making the auxiliary space usage constant. Therefore, the overall space complexity is O(1).

Edge Cases

Case	How to Handle
Null or empty string input	Return 0, as no characters need to be deleted to have at most K distinct characters in an empty string.
K is zero	Return the length of the string, as all characters must be deleted to have zero distinct characters.
K is greater than or equal to the number of distinct characters in the string	Return 0, as no deletions are needed to satisfy the condition.
String contains all identical characters	Return 0, as the string already has only one distinct character (or is empty).
String with a very large number of distinct characters and small K (e.g., string of length 1000 with 999 distinct chars, K=1)	The sliding window approach or frequency counting should efficiently handle this, avoiding unnecessary iterations by prioritising less frequent characters for deletion
String contains Unicode characters	Ensure the character counting method (e.g., HashMap or array) can handle the full range of Unicode characters; the algorithm should work with any character set.
Very long string with many repeating sequences of different characters and a small k	The frequency counting or sliding window will need to dynamically adjust to minimize deletions and potentially have time limit issues if poorly implemented.
Input string contains only special characters	Algorithm should treat all characters equally; the counting mechanism handles any character as input.

Null or empty string input

How to Handle:

Return 0, as no characters need to be deleted to have at most K distinct characters in an empty string.

K is zero

How to Handle:

Return the length of the string, as all characters must be deleted to have zero distinct characters.

K is greater than or equal to the number of distinct characters in the string

How to Handle:

Return 0, as no deletions are needed to satisfy the condition.

String contains all identical characters

How to Handle:

Return 0, as the string already has only one distinct character (or is empty).

String with a very large number of distinct characters and small K (e.g., string of length 1000 with 999 distinct chars, K=1)

How to Handle:

The sliding window approach or frequency counting should efficiently handle this, avoiding unnecessary iterations by prioritising less frequent characters for deletion

String contains Unicode characters

How to Handle:

Ensure the character counting method (e.g., HashMap or array) can handle the full range of Unicode characters; the algorithm should work with any character set.

Very long string with many repeating sequences of different characters and a small k

How to Handle:

The frequency counting or sliding window will need to dynamically adjust to minimize deletions and potentially have time limit issues if poorly implemented.

Input string contains only special characters

How to Handle:

Algorithm should treat all characters equally; the counting mechanism handles any character as input.