3545. Minimum Deletions for At Most K Distinct Characters

中文文档

Description

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.

Solutions

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.

The time complexity is $O(|\Sigma| \times \log |\Sigma|)$, and the space complexity is $O(|\Sigma|)$, where $|\Sigma|$ is the size of the character set. In this problem, $|\Sigma| = 26$.

Python3

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

Java

class Solution {
    public int minDeletion(String s, int k) {
        int[] cnt = new int[26];
        for (char c : s.toCharArray()) {
            ++cnt[c - 'a'];
        }
        Arrays.sort(cnt);
        int ans = 0;
        for (int i = 0; i + k < 26; ++i) {
            ans += cnt[i];
        }
        return ans;
    }
}

C++

class Solution {
public:
    int minDeletion(string s, int k) {
        vector<int> cnt(26);
        for (char c : s) {
            ++cnt[c - 'a'];
        }
        ranges::sort(cnt);
        int ans = 0;
        for (int i = 0; i + k < 26; ++i) {
            ans += cnt[i];
        }
        return ans;
    }
};

Go

func minDeletion(s string, k int) (ans int) {
	cnt := make([]int, 26)
	for _, c := range s {
		cnt[c-'a']++
	}
	sort.Ints(cnt)
	for i := 0; i+k < len(cnt); i++ {
		ans += cnt[i]
	}
	return
}

TypeScript

function minDeletion(s: string, k: number): number {
    const cnt: number[] = Array(26).fill(0);
    for (const c of s) {
        ++cnt[c.charCodeAt(0) - 97];
    }
    cnt.sort((a, b) => a - b);
    return cnt.slice(0, 26 - k).reduce((a, b) => a + b, 0);
}