[Java] ✅ 100% ✅ SLIDING WINDOW ✅ FASTEST ✅ BEST ✅ CLEAN CODE
Approach\n1. Get the frequency of the characters: charFreq[].\n2. Sort and trim (do not include 0 freq) in the charFreq. Now charFreq is like [1,1,3,4,7,8,9]\n3
# Approach\n1. Get the frequency of the characters: charFreq[].\n2. Sort and trim (do not include 0 freq) in the charFreq. Now charFreq is like [1,1,3,4,7,8,9]\n3. Looking at K (max diff), we see this is actually a window. (left, right): [1,1,3,4,7,8,9]\n    - at freq of 1 (left) , you can have a max freq of 1 + k (right)\n    - eg: k  = 5, at index[0] (1) you window can be opened to index [3] (4). At index [4] the window is not valid: 7-1 > 5\n4. Compute the cost of eliminating all elements at the left of left.\n    - For right index, everything on the right needs to be removed until freq[right]\n5. ! However, is it efficient to lower all elements to index[3] = 4 ? Our window could expant until a freq of 6 (1 + 5).\n    So, in fact, everything on the right of right needs to be lowered at freq[left] + k, and not at freq[right].\n6. Use this sliding window and find the min deletions.\n\n# Complexity\n- Time complexity:$$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:$$O(1)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```java []\n    public int minimumDeletions(String word, int k) {\n        int minDeletions = Integer.MAX_VALUE;\n        int[] charFreq = getCharFreq(word);\n        int[] prefixSum = new int[charFreq.length];\n        prefixSum[0] = charFreq[0];\n        for (int i = 1; i <prefixSum.length; i++) {\n            prefixSum[i] = prefixSum[i-1] + charFreq[i];\n        }\n        for(int left = 0, right = 0; left < charFreq.length; left++) {\n            while (right < charFreq.length && charFreq[left] + k > charFreq[right]) {\n                right++;\n            }\n            minDeletions = Math.min(minDeletions, findMinDeletions(charFreq, left, Math.max(0, right - 1), prefixSum, k));\n        }\n        return minDeletions;\n    }\n\n    private int findMinDeletions(int[] charFreq, int left, int right, int[] prefixSum, int k) {\n        int deletedOnLeft = left == 0 ? 0 : prefixSum[left - 1], deletedOnRight;\n        if (right == charFreq.length - 1) {\n            deletedOnRight = 0;\n        } else {\n            int rightTarget = Math.min(charFreq[left] + k, charFreq[right + 1]);\n            deletedOnRight = (prefixSum[prefixSum.length - 1] - prefixSum[right]) - rightTarget * ((charFreq.length - 1) - right);\n        }\n        return deletedOnLeft + deletedOnRight;\n    }\n\n    private int[] getCharFreq(String word) {\n        int[] charFreq = new int[26];\n        for (int i = 0; i < word.length(); i++) {\n            charFreq[word.charAt(i) - \'a\']++;\n        }\n        Arrays.sort(charFreq);\n        int nonZeroIndex = 0;\n        while(charFreq[nonZeroIndex] == 0) {\n            nonZeroIndex++;\n        }\n        return Arrays.copyOfRange(charFreq, nonZeroIndex, charFreq.length);\n    }\n```
['Two Pointers', 'Sliding Window', 'Java']