C++ 100% Faster | Easy Step By Step Explanation
Intuition\nThe key to solve this problem lies in identifying the discrepancies between character frequencies. A string is k-special if the absolute difference b
# Intuition\nThe key to solve this problem lies in identifying the discrepancies between character frequencies. A string is k-special if the absolute difference between the frequencies of any two characters (|freq(i) - freq(j)|) is less than or equal to k. Therefore, we need to find the minimum number of deletions required to minimize these frequency differences.\n\n# Approach\n1. **Character Frequency Count:**\n    - Create a hash table (unordered_map) to store the frequency of each character in the string (word).\n    - Iterate through the string and update the corresponding character\'s count in the hash table.\n2. **Frequency Array and Sorting:**\n    - Extract the character frequencies from the hash table and store them in a separate vector (freq).\n    - Sort the frequency vector (freq) in descending order. This ensures we focus on characters with the highest frequencies first, as they potentially contribute to the most deletions.\n3. **Iterative Comparison:**\n    - Initialize a variable ans to store the minimum number of deletions (initially set to positive infinity).\n    - **Iterate through the sorted frequency vector (freq):**\n        - **For each frequency num in freq:**\n            - Initialize a counter cnt to track the number of deletions needed for the current frequency.\n            - **Iterate through the entire frequency vector again:**\n                - **If the difference between the current frequency (num) and another frequency (freq[j]) is greater than k (freq[j] - num > k):**\n                    - This indicates a violation of the k-special condition. We need to delete characters with frequency freq[j] down to num + k. Calculate the number of deletions by subtracting the allowed frequency (num + k) from the actual frequency (freq[j]).\n                 - **If the current frequency (num) is higher than another frequency (freq[j]): (num > freq[j])**\n                    - This also violates the k-special condition because characters with lower frequency cannot exceed the allowed difference. We need to delete all characters with frequency freq[j].\n            - Update cnt with the total number of deletions calculated for the current frequency (num).\n            - Update ans with the minimum number of deletions encountered so far (ans = min(ans, cnt)).\n            - If cnt is zero (no deletions needed), stop iterating further as we\'ve found a solution where the current frequency doesn\'t require any deletions.\n4. **Return Minimum Deletions:**\n    - After iterating through all frequencies, return the minimum number of deletions found (ans).\n\n# Complexity\n- Time complexity:  **O(26*26)** \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```\n#pragma GCC optimize("O3", "unroll-loops")\nclass Solution {\npublic:\n  int minimumDeletions(string word, int k) {\n    unordered_map<char, int> mp;\n    for (auto it : word) {\n      mp[it]++;\n    }\n\n    vector<int> freq;\n    for (auto it : mp) {\n      freq.push_back(it.second);\n    }\n    sort(freq.begin(), freq.end(), greater<int>());\n\n    int ans = INT_MAX; \n\n    for (int i = 0; i < freq.size(); i++) {\n      int num = freq[i]; \n      int cnt = 0;\n\n      for (int j = 0; j < freq.size(); j++) {\n        if (freq[j] - num > k) {\n          cnt += freq[j] - (num + k);\n        } \n        else if (num > freq[j]) {\n          cnt += freq[j];\n        }\n      }\n      ans = min(ans, cnt);\n      if (cnt == 0) {\n        break;\n      }\n    }\n\n    return ans;\n  }\n};\nauto init = []() {\n    ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return \'c\';\n}();\n```\n![Please Upvote2.jpeg](https://assets.leetcode.com/users/images/c6c2b3ca-5d40-4a4e-901a-484c87ffb616_1710647333.1872308.jpeg)\n
['Array', 'Math', 'C++']