Simple C++ solution, very intuitive
Intuition\n Describe your first thoughts on how to solve this problem. \nAt the beginning the problem seems a little bit scary, infact it tells us to consider a
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nAt the beginning the problem seems a little bit scary, infact it tells us to consider all the pairwise indeces and confront them.\nIn reality we don\'t have to confront all the possible indeces, but just the letters.\n\n**The main intuition** is to transform the problem from a "confront all the letters in the indeces" problem to a "count the letters and confront the frequencies" problem.\nNow we don\'t care anymore about the letters, but we care about their frequencies and the fact that the difference between the minimum and the maximum frequencies must not be above $$k$$.\n\n**The last step** to conclude the problem is the following: we can $$delete$$ all the characters of the same type or $$reduce$$ them to enter the interval between the minimum and the maximum frequencies.\nIn order to do that I try every single frequency to be the minimum and then calculate how the others can enter the interval and when I pass from a frequency to another, it is like deleting all the characters of the first frequency because now they cannot be in the interval anymore.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nFirst of all I have counted all the letters and stored in a vector, then I sorted it in increasing order.\nAt this point I have initialized the variable $$ans$$ (the answer of the problem) to infinite and $$startDel$$ as 0.\nAt each iteration the current deleted elements $$curDel$$ is initialized with the already deleted characters ($$startDel$$) then I try to reduce the other characters to enter the interval represented by $$[cnt[i], cnt[i] + k]$$, so when a frequency is outside the limit a deletion is needed.\nAt the end of the iteration I update the answer and the $$startDel$$ characters because I have to pass to the next iteration.\n\n# Complexity\n- Time complexity:\n$$O(n)$$ with n = length of the string\nBecause to read all the string I use $$O(n)$$ time, but then all the other operations are constant because they are operating on constant numbers\n\n- Space complexity:\n$$O(1)$$ it is constant because I have always to allocate a vector of 26 elements\n\n# Code\n```\nclass Solution {\npublic:\n    int minimumDeletions(string word, int k) {\n        vector<int> cnt(26);\n        \n        for(char c : word) {\n            cnt[c - \'a\']++;\n        }\n        \n        sort(cnt.begin(), cnt.end());\n        int ans = 1e9;\n        int startDel = 0;\n        \n        for(int i = 0; i < 26; i++) {\n            int curDel = startDel;\n            int topLimit = cnt[i] + k;\n            for(int j = i + 1; j < 26; j++) {\n                if(topLimit < cnt[j]) curDel += cnt[j] - topLimit;\n            }\n            ans = min(ans, curDel);\n            startDel += cnt[i];\n        }\n        \n        return ans;\n    }\n};\n```
['String', 'Greedy', 'C++']