🚀 Mastering Character Deletions: The Ultimate Strategy to Minimize Changes! 🔥Easy Explanation!
IntuitionThe goal of this problem is to minimize the number of character deletions required to make the frequency difference between the most and least occurrin
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The goal of this problem is to minimize the number of character deletions required to make the frequency difference between the most and least occurring characters at most k. This is done by removing characters with either the lowest or highest frequency.



# Approach
<!-- Describe your approach to solving the problem. -->
Count character frequencies: We first count the frequency of each character in the input string.
Sort the frequencies: Sorting helps in efficiently removing either the least or most frequent character.
Use recursion with memoization:

We use a recursive function func(i, j, list, k, dp) where:
i represents the index of the smallest frequency.
j represents the index of the largest frequency.

dp[i][j] stores the minimum deletions required for the range [i, j].

If the frequency difference list[j] - list[i] is already ≤ k, we return 0 (no deletions needed).

Otherwise, we have two options:
Remove the character with the smallest frequency (list[i]) and recurse on the remaining range [i+1, j].

Reduce the highest frequency list[j] to list[i] + k and recurse on [i, j-1].

We take the minimum deletions from both choices and store the result in dp[i][j].


# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
O(26*26)

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
O(27*27)

# Code
```java []
import java.util.*;

class Solution {
    public int func(int i, int j, List<Integer> list, int k, int[][] dp) {
        // Base case: If the difference between max and min frequency is within k, no deletions needed
        if (list.get(j) - list.get(i) <= k) return 0;

        // Return the already computed result to avoid recomputation
        if (dp[i][j] != -1) return dp[i][j];

        // Option 1: Remove the character with the smallest frequency
        int removeMin = list.get(i) + func(i + 1, j, list, k, dp);

        // Option 2: Reduce the highest frequency to (list[i] + k) and delete the excess
        int removeMax = (list.get(j) - (list.get(i) + k)) + func(i, j - 1, list, k, dp);

        // Store and return the minimum deletions needed
        return dp[i][j] = Math.min(removeMin, removeMax);
    }

    public int minimumDeletions(String word, int k) {
        // Step 1: Count frequency of each character
        int[] arr = new int[26]; // Array to store character frequencies
        for (int i = 0; i < word.length(); i++) {
            arr[word.charAt(i) - 'a']++;
        }

        // Step 2: Store non-zero frequencies in a list
        List<Integer> list = new ArrayList<>();
        for (int i : arr) {
            if (i > 0) {
                list.add(i);
            }
        }

        // Step 3: Sort the list to easily manipulate min and max frequencies
        Collections.sort(list);

        // Step 4: Initialize DP array with -1 (for memoization)
        int[][] dp = new int[27][27]; // Maximum size is at most 26 unique characters
        for (int[] a : dp) {
            Arrays.fill(a, -1);
        }

        // Step 5: Call the recursive function starting from the full range
        return func(0, list.size() - 1, list, k, dp);
    }
}

```
['String', 'Dynamic Programming', 'Sorting', 'Counting', 'Java']