LeetCode－1647. Minimum Deletions to Make Character Frequencies Unique

難度:Medium

描述:字串 s 中，不存在頻次相同的字元，就稱 s 是優質字串。

給一個字串 s ，回傳使 s 成為優質字串需要刪除的最小字元數。

字串中的字元頻次，指該字元在字串中出現的次數。例："aabb"中，'a'的頻次是2；'b'的頻次是1。

方法一：(Map & Set)

思路：

1.先統計字元的頻次

2.Set 逐一Join 不同頻次的字元。

3.若頻次的字元存在，則該字元頻次減少至Set 不存在的頻次。

Runtime : 70 ms        (45.86%)

Memory : 17.60 MB  (14.93%)

  

class Solution {
public:
    int minDeletions(string s) {
        int ans = 0;
        unordered_map<char, int> stringMap;
        set<int> myset;
        for(const auto& c : s){
            stringMap[c]++;
        }
        for (const auto& s : stringMap) {
            int freq = s.second;
            while( freq>0 && myset.find(freq) != myset.end() ){
                freq--;
                ans++;
            }
            myset.insert(freq);
        }
        return ans;
    }
};