3545. Minimum Deletions for At Most K Distinct Characters LeetCode Solution

3 months ago
LeetCode Admin
3 minutes

In this guide, you will get 3545. Minimum Deletions for At Most K Distinct Characters LeetCode Solution with the best time and space complexity. The solution to Minimum Deletions for At Most K Distinct Characters problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Minimum Deletions for At Most K Distinct Characters solution in C++
  4. Minimum Deletions for At Most K Distinct Characters solution in Java
  5. Minimum Deletions for At Most K Distinct Characters solution in Python
  6. Additional Resources
3545. Minimum Deletions for At Most K Distinct Characters LeetCode Solution image

Problem Statement of Minimum Deletions for At Most K Distinct Characters

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.

See also  1838. Frequency of the Most Frequent Element LeetCode Solution

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.

Complexity Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(26) = O(1)

3545. Minimum Deletions for At Most K Distinct Characters LeetCode Solution in C++

class Solution {
 public:
  int minDeletion(string s, int k) {
    unordered_map<char, int> count;

    for (const char c : s)
      ++count[c];

    if (count.size() <= k)
      return 0;

    vector<int> freqs;

    for (const auto& [_, freq] : count)
      freqs.push_back(freq);

    ranges::sort(freqs);
    return accumulate(freqs.begin(), freqs.begin() + freqs.size() - k, 0);
  }
};
/* code provided by PROGIEZ */

3545. Minimum Deletions for At Most K Distinct Characters LeetCode Solution in Java

class Solution {
  public int minDeletion(String s, int k) {
    Map<Character, Integer> count = new HashMap<>();

    for (final char c : s.toCharArray())
      count.merge(c, 1, Integer::sum);

    if (count.size() <= k)
      return 0;

    List<Integer> freqs = new ArrayList<>(count.values());
    Collections.sort(freqs);
    return freqs.subList(0, freqs.size() - k).stream().mapToInt(Integer::intValue).sum();
  }
}
// code provided by PROGIEZ

3545. Minimum Deletions for At Most K Distinct Characters LeetCode Solution in Python

class Solution:
  def minDeletion(self, s: str, k: int) -> int:
    count = collections.Counter(s)
    if len(count) <= k:
      return 0
    freqs = sorted(count.values())
    return sum(freqs[:len(freqs) - k])
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Similar: