(LeetCode 每日一题) 3085. 成为 K 特殊字符串需要删除的最少字符数 (贪心、哈希表)

思路；哈希表存储每个字母出现的次数，然后升序排序。枚举最小的出现次数v[i]，那么最大的出现次数上限为v[i]+k。维护最多的合法字符数量mx，那么最少的删除数量就是word.size()-mx。

C++版本：

class Solution {
public:int minimumDeletions(string word, int k) {// 哈希表存储每个字母出现的次数vector<int> v(26,0);for(auto c:word){v[c-'a']++;}// 升序排序sort(v.begin(),v.end());// 维护最多的合法字符数量mxint mx=0;// 枚举最小的出现次数v[i]for(int i=0;i<26;i++){int sum=0;// 最大的出现次数上限为v[i]+kfor(int j=i;j<26;j++){sum+=min(v[i]+k,v[j]);}mx=max(mx,sum);}return word.size()-mx;}
};

JAVA版本：

class Solution {public int minimumDeletions(String word, int k) {int[] v=new int[26];for(var c:word.toCharArray()){v[c-'a']++;}Arrays.sort(v);int mx=0;for(int i=0;i<26;i++){int sum=0;for(int j=i;j<26;j++){sum+=Math.min(v[i]+k,v[j]);}mx=Math.max(mx,sum);}return word.length()-mx;}
}

Go版本：

func minimumDeletions(word string, k int) int {v:=make([]int,26)for _,c:=range word {v[c-'a']++}slices.Sort(v)mx:=0for i:=0;i<26;i++ {sum:=0for j:=i;j<26;j++ {sum+=min(v[i]+k,v[j])}mx=max(mx,sum)}return len(word)-mx
}