Explained-Solution with Intuition || AC ✅
Intuition\n  * We want to make freq[i] - freq[j] <=k for all i and j. \n  * find frequency of all characters and sort them. \n  * At max we have 26 characters s
# Intuition\n  * We want to make ```freq[i] - freq[j] <=k ``` for all `i` and `j`. \n  * find frequency of all characters and sort them. \n  * At max we have 26 characters so , size of the `freq` can be of `26`.\n  * Now , as we can only decrease the freq of characaters , so first we choose `freq[0]` as `minimum`.\n  \n  * ``` ans+=max(0 , freq[i] - freq[0] - k) ``` \n \n\n* so , minimize the ans by considering `freq[i]` as minimum and deleting all previous frequencies which is `preSum`.  \n\n* ```ans = min(ans  , completely deleted till ith index + partially deleted from i+1 to n)```\n\n# Complexity\n- Time complexity:\n    ```O(n) + O(26log26) ~ O(n)```\n\n- Space complexity:\n    ```O(n)```\n\n# Code\n```\nclass Solution {\npublic: \n    \n\n    int minimumDeletions(string s , int k) {\n         \n        int n = s.length(); \n        map<int,int> map; \n        \n        for(char ch : s){\n            map[ch]++; \n        } \n        \n        vector<int> freq; \n        \n        for(auto it : map){\n            freq.push_back(it.second); \n        }  \n         \n        // Sort the frequencies\n        sort(freq.begin() , freq.end()); \n        \n        // If we take minimum as freq[0] and convert all other frequencies \n        // such that abs(freq[0] - freq[i]) <=k\n        int ans = 0;   \n        for(int i = 0 ; i <  freq.size() ; i++){\n            ans+=max(0 , freq[i] - freq[0] - k); \n        }\n        \n        // preSum denotes that how many frequencies we already deleted \n        // completely  till Ith index\n        int preSum = 0; \n        \n        for(int i = 0 ; i < freq.size() ; i++){ \n              \n             int temp = preSum;  \n\n            //  we consider freq[i] as new minimum\n\n             for(int j = i ; j < freq.size() ; j++){\n                 temp+=max(0 ,  freq[j]-freq[i] - k); \n             } \n             \n             ans = min(ans , temp); \n             preSum+=freq[i]; \n        }\n        \n        return ans; \n        \n        \n    }\n};\n```
['Hash Table', 'Sorting', 'Prefix Sum', 'C++']