Leetcode 1770 Solution

This article provides solution to leetcode question 1770 (minimum-deletions-to-make-character-frequencies-unique)
Categories:
Tags:
Access this page by simply typing in "lcs 1770" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/minimum-deletions-to-make-character-frequencies-unique

Solution

class Solution {
public:
    int minDeletions(string s) {
        map<char, int> freq;
        for (auto it = s.begin(); it != s.end(); it++)
            freq[*it] += 1;

        map<int, int> freqfreq;
        for (auto it = freq.begin(); it != freq.end(); it++)
            freqfreq[it->second] += 1;

        int ans = 0;
        while (freqfreq.empty() == false)
        {
            const auto it = std::prev( freqfreq.end() );

            if (it->second > 1)
            {
                int freq = it->first;
                int cnt = it->second - 1;
                ans += cnt;

                if (freq > 1)
                    freqfreq[freq - 1] += cnt;
            }
            freqfreq.erase(it);
        }

        return ans;
    }
};