Skip to content

3545. Minimum Deletions for At Most K Distinct Characters 👍

  • Time: $O(n)$
  • Space: $O(26) = O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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();
  }
}

1
2
3
4
5
6
7
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])