[Java Solution] Dynamic Programming With Clear Explanation
Intuition\nThe challenge involves balancing the frequencies of characters in a string to make it "k-special," where the frequency difference between any two cha
# Intuition\nThe challenge involves balancing the frequencies of characters in a string to make it "k-special," where the frequency difference between any two characters does not exceed `k`. The initial step is to understand the frequency distribution of characters, guiding the deletions needed to achieve this balance.\n\n# Approach\nThe solution starts by calculating the frequency of each character and then sorting these frequencies. Using dynamic programming and a 2D memoization array, the algorithm finds the minimum number of deletions required. \nIt compares two main actions for each step: \n- deleting from the high-frequency end (right) \n- deleting from the low-frequency end (left)\n\nrecursively determining the minimum deletions needed for each subarray.\n\n# Complexity\n- Time complexity: $$O(n)$$\nThe complexity is due to traversing the entire `word`($$O(n)$$) and sorting the frequency array ($$O(26 \\log 26)$$) and the dynamic programming solution ($$O(26^2)$$ for all subarray combinations).\n\n- Space complexity: $$O(26^2) \\approx O(1)$$\nThe space complexity is determined by the size of the 2D memoization array and the stack of recursive calls, which is a constant $$O(26^2)$$, independent of the input size.\n\n\n# Code\n```\nclass Solution {\n    final int MAX = 100_001;\n    public int minimumDeletions(String word, int k) {\n        int[] freq = new int[26];\n        for (char c : word.toCharArray()) {\n            freq[c - \'a\']++;\n        }\n        \n        Arrays.sort(freq);\n        int l = 0, r = 25;\n        int[][] memo = new int[26][26];\n        for (int i = 0; i < 26; i++) {\n            Arrays.fill(memo[i], MAX);\n        }\n        int deletion = getMinDeletion(freq, 0, 25, k, memo);\n        \n        return deletion;\n    }\n    \n    private int getMinDeletion(int[] freq, int l, int r, int k, int[][] memo) {\n        if (memo[l][r] != MAX) return memo[l][r];\n        if (freq[r] - freq[l] <= k) return 0;\n        \n        // first plan is deleting from the right:\n        int plan1 = freq[r] - (freq[l] + k) + getMinDeletion(freq, l, r - 1, k, memo);\n        // second plan is deleting from the left:\n        int plan2 = freq[l] + getMinDeletion(freq, l + 1, r, k, memo);\n        \n        memo[l][r] = Math.min(plan1, plan2);\n        \n        return memo[l][r];\n    }\n}\n```
['Dynamic Programming', 'Java']