Binary Search || Prefix Sum || nlog(n) solution || Iterate over all possible values as the minimum
Intuition\n Describe your first thoughts on how to solve this problem. \n\nAfter computing the frequency of characters in the string, we can convert the problem
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\nAfter computing the frequency of characters in the string, we can convert the problem to the following:\n\nGiven an array nums and an integer k, find the minimum number of operations to make |nums[i] - nums[j]| <= k for any pair of i and j.\n\nThe intuition is to traverse over all possible values of nums[i] being the minimum and find the min ops. A brute force solution will take o(n) calculate ops for any given nums[i], bring the total time complexity to o(n^2). We can use binary search and prefix sum to make the operation o(log(n)).\n\nAfter sorting nums, for any given nums[i], we have to delete all values on its left, meaning ops_left = sum[0, i -1]. Then we use binary search to find the first element at idx j bigger than nums[i] + k. ops_right = sum[j:n-1] - count[j:n-1]*(nums[i] + k).\n\n# Code\n```\nclass Solution {\n    public int bs(int[] freqs, int i, int target){\n        int l = -1;\n        int r = freqs.length;\n        l = i;\n        while(l < r){\n            int mid = (l + r)/2;\n            if(freqs[mid] > target){\n                r = mid;\n            }else{\n                l = mid + 1;\n            }\n        }\n        return r;\n    }\n\n    public int findOps(int[] freqs, int k){\n\n        int ans = Integer.MAX_VALUE;\n        int[] prefix = new int[freqs.length + 1];\n        prefix[0] = 0;\n        int sum = 0;\n        for(int i = 0; i < freqs.length; i++){\n            sum += freqs[i];\n            prefix[i+1] = sum;\n        }\n\n        for(int i = 0; i < freqs.length; i++){         \n            int curr = 0;\n            int target = freqs[i] + k;\n            int idx = bs(freqs, i, target);\n            int cnt = freqs.length - idx;\n            int right_sum = prefix[freqs.length] - prefix[idx];\n            curr += (right_sum - cnt*target);\n            curr += prefix[i];\n            ans = Math.min(ans, curr);\n        }\n\n        return ans;\n    }\n    \n    public int minimumDeletions(String word, int k) {\n        int[] freqs = new int[26];\n        for(int i = 0; i < word.length(); i++){\n            char c = word.charAt(i);\n            freqs[c - \'a\']++;\n        }\n        \n        Arrays.sort(freqs);\n        int ans = findOps(freqs, k);\n        return ans;\n    }\n}\n```
['Binary Search', 'Prefix Sum', 'Java']