1import java.util.ArrayList;
2import java.util.List;
3
4class Solution {
5    // List to store the frequencies of characters in the input word
6    private List<Integer> characterFrequencies = new ArrayList<>();
7
8    // Method to calculate the minimum number of deletions required
9    public int minimumDeletions(String word, int k) {
10        // Array to store frequency of each character in the English alphabet
11        int[] frequencyArray = new int[26];
12        int wordLength = word.length();
13      
14        // Calculate frequency of each character in the input word
15        for (int i = 0; i < wordLength; ++i) {
16            ++frequencyArray[word.charAt(i) - 'a'];
17        }
18      
19        // Add non-zero frequencies to the characterFrequencies list
20        for (int frequency : frequencyArray) {
21            if (frequency > 0) {
22                characterFrequencies.add(frequency);
23            }
24        }
25      
26        // Initialize the answer with the length of the word
27        int minimumDeletions = wordLength;
28      
29        // Find the minimum deletions possible by checking for every potential value `v` from 0 to word length
30        for (int i = 0; i <= wordLength; ++i) {
31            // Update minimumDeletions with the smaller value between the current and the new calculation from helper function `f`
32            minimumDeletions = Math.min(minimumDeletions, calculateDeletions(i, k));
33        }
34        return minimumDeletions;
35    }
36
37    // Helper method to calculate deletions given a threshold `v` and limit `k`
38    private int calculateDeletions(int v, int k) {
39        int deletions = 0;
40      
41        // Iterate over each frequency in the list
42        for (int frequency : characterFrequencies) {
43            // If the frequency is less than `v`, add the full frequency to deletions
44            if (frequency < v) {
45                deletions += frequency;
46            }
47            // If the frequency exceeds `v + k`, calculate the deletions needed to reduce it
48            else if (frequency > v + k) {
49                deletions += frequency - v - k;
50            }
51        }
52        return deletions;
53    }
54}
55

1#include <vector>
2#include <string>
3#include <algorithm>  // For std::min
4using namespace std;
5
6class Solution {
7public:
8    int minimumDeletions(string word, int k) {
9        // Array to store the frequency of each character in the word.
10        int frequency[26] = {};
11
12        // Increment the appropriate frequency count for each character in 'word'.
13        for (char& c : word) {
14            ++frequency[c - 'a'];
15        }
16
17        // Vector to store the frequencies of all the characters that appear in the word.
18        vector<int> characterFrequencies;
19        for (int freq : frequency) {
20            if (freq > 0) {
21                characterFrequencies.push_back(freq);
22            }
23        }
24
25        int wordSize = word.size();
26        int minimumDeletionsResult = wordSize;
27
28        // Lambda function to calculate deletions needed to balance frequencies.
29        auto calculateDeletions = [&](int targetFrequency) {
30            int deletions = 0;
31            for (int freq : characterFrequencies) {
32                if (freq < targetFrequency) {  // Frequency is too low
33                    deletions += freq;
34                } else if (freq > targetFrequency + k) {  // Frequency too high to be adjusted by 'k'
35                    deletions += (freq - targetFrequency - k);
36                }
37            }
38            return deletions;
39        };
40
41        // Try all target frequencies from 0 to the size of the word to determine minimum deletions.
42        for (int target = 0; target <= wordSize; ++target) {
43            minimumDeletionsResult = min(minimumDeletionsResult, calculateDeletions(target));
44        }
45
46        return minimumDeletionsResult;
47    }
48};
49

1// Function to calculate the minimum number of deletions required from the word
2// such that for any character frequency `x`, either `x < v` or `x > v + k`
3function minimumDeletions(word: string, k: number): number {
4    // Create an array to store the frequency of each letter in the word
5    const frequency: number[] = Array(26).fill(0);
6  
7    // Populate the frequency array
8    for (const ch of word) {
9        frequency[ch.charCodeAt(0) - 97]++;
10    }
11  
12    // Filter out zero frequencies, only keep those greater than zero
13    const nums = frequency.filter(count => count > 0);
14  
15    // Helper function to calculate deletions needed for a given target value v
16    const f = (v: number): number => {
17        let deletions = 0;
18        for (const x of nums) {
19            if (x < v) {
20                deletions += x;
21            } else if (x > v + k) {
22                deletions += x - v - k;
23            }
24        }
25        return deletions;
26    };
27  
28    // Calculate the minimum deletions required by considering all possible target frequencies
29    return Math.min(...Array.from({ length: word.length + 1 }, (_, i) => f(i)));
30}
31