Minimum Deletions to make String K-Special: Efficient HashMap Algo
Intuition\nThe intuition behind this code is to find the minimum number of deletions required to make the frequency of each character in the string word at most
# Intuition\nThe intuition behind this code is to find the minimum number of deletions required to make the frequency of each character in the string `word` at most `k`.\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n1. **Initialize Variables**: \nThe code initializes a dictionary `map` to store the frequency of each character in `word`, a list `vals` to store the frequencies, and integers `sumOfLess`, `ans`, and `n` to store the sum of frequencies less than the current frequency, the minimum number of deletions, and the number of distinct characters in `word` respectively.\n2. **Count Frequencies**: \nThe code then iterates over the characters in `word` and increments their frequency in `map`.\n3. **Store Frequencies**: \nThe code stores the frequencies in `vals` and sorts `vals`.\n4. **Calculate Minimum Deletions**: \nThe code iterates over `vals`. For each frequency `vals[i]`, it calculates the sum of frequencies less than `vals[i]` and the sum of differences between frequencies greater than `vals[i]` and `k`. It updates `ans` with the minimum of `ans` and the calculated sum.\n5. **Return Minimum Deletions**: \nThe code returns `ans`, which represents the minimum number of deletions required to make the frequency of each character at most `k`.\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: $$O(N \\log N)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(N)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\npublic class Solution {\n    public int MinimumDeletions(string word, int k) {\n        Dictionary<char, int> map = new Dictionary<char, int>();\n        foreach(char ch in word) {\n            if(!map.ContainsKey(ch))\n                map[ch] = 0;\n            map[ch]++;\n        }\n        \n        List<int> vals = new List<int>();\n        foreach(var item in map)\n            vals.Add(item.Value);\n        vals.Sort();\n        \n        int sumOfLess = 0;\n        int ans = int.MaxValue;\n        int n = vals.Count;\n        for(int i = 0; i < n; i++) {\n            if(i > 0)\n                sumOfLess += vals[i - 1];\n            int sum = sumOfLess;\n            for(int j = i + 1; j < n; j++) {\n                if(vals[j] - vals[i] > k)\n                    sum += vals[j] - vals[i] - k;\n            }\n            ans = Math.Min(ans, sum);\n        }\n        return ans;\n    }\n}\n```
['Hash Table', 'String', 'Sorting', 'C#']