Problem

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

1
2
3
4
5
6

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

1
2
3
4
5

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

1
2
3
4
5
6

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.

Examples

Solution

Method 1 – Greedy Frequency Removal

Intuition

To minimize deletions, we want to keep the k most frequent characters and remove all others. By sorting character frequencies, we can efficiently determine which characters to delete.

Approach

  1. Count the frequency of each character in s.
  2. If the number of distinct characters is less than or equal to k, return 0.
  3. Sort the frequencies in ascending order.
  4. Delete all occurrences of the least frequent characters until only k distinct characters remain.
  5. Sum the frequencies of the deleted characters for the answer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    int minDeletions(string s, int k) {
        unordered_map<char, int> freq;
        for (char c : s) freq[c]++;
        if (freq.size() <= k) return 0;
        vector<int> f;
        for (auto& p : freq) f.push_back(p.second);
        sort(f.begin(), f.end());
        int ans = 0;
        for (int i = 0; i < f.size() - k; ++i) ans += f[i];
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

func minDeletions(s string, k int) int {
    freq := map[rune]int{}
    for _, c := range s { freq[c]++ }
    if len(freq) <= k { return 0 }
    f := []int{}
    for _, v := range freq { f = append(f, v) }
    sort.Ints(f)
    ans := 0
    for i := 0; i < len(f)-k; i++ { ans += f[i] }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    public int minDeletions(String s, int k) {
        Map<Character, Integer> freq = new HashMap<>();
        for (char c : s.toCharArray()) freq.put(c, freq.getOrDefault(c, 0)+1);
        if (freq.size() <= k) return 0;
        List<Integer> f = new ArrayList<>(freq.values());
        Collections.sort(f);
        int ans = 0;
        for (int i = 0; i < f.size()-k; ++i) ans += f.get(i);
        return ans;
    }
}
1
2
3
4
5
6
7
8
9

class Solution {
    fun minDeletions(s: String, k: Int): Int {
        val freq = mutableMapOf<Char,Int>()
        for (c in s) freq[c] = freq.getOrDefault(c,0)+1
        if (freq.size <= k) return 0
        val f = freq.values.sorted()
        return f.take(f.size-k).sum()
    }
}
1
2
3
4
5
6
7
8

class Solution:
    def minDeletions(self, s: str, k: int) -> int:
        from collections import Counter
        freq = Counter(s)
        if len(freq) <= k:
            return 0
        f = sorted(freq.values())
        return sum(f[:len(f)-k])
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

impl Solution {
    pub fn min_deletions(s: String, k: i32) -> i32 {
        use std::collections::HashMap;
        let mut freq = HashMap::new();
        for c in s.chars() { *freq.entry(c).or_insert(0) += 1; }
        if freq.len() as i32 <= k { return 0; }
        let mut f: Vec<i32> = freq.values().cloned().collect();
        f.sort();
        f.iter().take(f.len()-k as usize).sum()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    minDeletions(s: string, k: number): number {
        const freq: Record<string, number> = {};
        for (const c of s) freq[c] = (freq[c] || 0) + 1;
        const keys = Object.keys(freq);
        if (keys.length <= k) return 0;
        const f = Object.values(freq).sort((a,b) => a-b);
        return f.slice(0, f.length-k).reduce((a,b) => a+b, 0);
    }
}

Complexity

  • ⏰ Time complexity: O(n + d log d) where n is the length of s and d is the number of distinct characters.
  • 🧺 Space complexity: O(d) for the frequency map.