Unique String Frequencies - Microsoft Top Interview Questions

                        Solution in C++ :

int solve(string s) {
    unordered_map<char, int> freq;
    for (auto& c : s) freq[c]++;
    vector<int> freqCounts;
    for (auto& p : freq) freqCounts.push_back(p.second);
    sort(freqCounts.rbegin(), freqCounts.rend());
    int ret = 0;
    int lastFreq = 1e9;
    for (int freq : freqCounts) {
        // freq must be at most lastFreq
        if (freq > lastFreq) {
            int rem = freq - lastFreq;
            ret += rem;
            freq -= rem;
        }
        lastFreq = max(0, freq - 1);
    }
    return ret;
}
                    

                        Solution in Java :

import java.util.*;

class Solution {
    public int solve(String s) {
        // how many times does char "i" appear?
        int[] occ = new int[26];
        for (char c : s.toCharArray()) occ[c - 'a'] += 1;

        // how many letters appear "i" times?
        int[] freq = new int[s.length() + 1];
        for (int i = 0; i < 26; i++) {
            if (occ[i] > 0)
                freq[occ[i]] += 1;
        }

        // greedy algorithim
        int ans = 0;
        for (int i = s.length(); i >= 1; i--) {
            if (freq[i] > 1) {
                ans += (freq[i] - 1);
                freq[i - 1] += (freq[i] - 1);
            }
        }
        return ans;
    }
}
                    

                        Solution in Python : 
                            
class Solution:
    def solve(self, s):

        freq = Counter(s)
        deletions = 0
        unique = set()
        for f in freq.values():
            if f in unique:
                while f in unique and f > 0:
                    f -= 1
                    deletions += 1
            unique.add(f)
        return deletions