O(n) with sorting beating 100%
IntuitionCount the freq of each letter, and handle the freqs.Approach
Count the freq of each letter.
Sort the freqs.
For each index in freqs, we must try to dro
# Intuition
Count the freq of each letter, and handle the freqs.
# Approach
1. Count the freq of each letter.
2. Sort the freqs.
3. For each index in freqs, we must try to drop off the freqs to its left, and meanwhile, we must do some cutting from the right of the remaining array.
4. For each index, the above two operations both have a cost. We add the costs, and that's the outcome for the index.
5. The result is the minimum value of the outcomes.
6. Since there are at most 26 letters, only the counting takes O(n). All the other operations take O(1).
# Complexity
- Time complexity:
O(n)
- Space complexity:
O(1)
# Code
```javascript []
/**
 * @param {string} word
 * @param {number} k
 * @return {number}
 */
var minimumDeletions = function(word, k) {
    const aCode = 97
    const table = {}
    for (let i = 0; i < 26; i++) {
        const ch = String.fromCharCode(i + aCode)
        table[ch] = 0
    }
    for (const ch of word)
        table[ch]++
    const freqs = [...Object.values(table)].filter(freq => freq !== 0)
    freqs.sort((a, b) => a - b)


    const len = freqs.length
    let result = Infinity

    freqs[-1] = 0
    let sumSF = 0
    for (let i = -1; i < len - 1; i++) {
        const freq = freqs[i]
        sumSF += freq
        
        let outcome = sumSF
        const leftFreq = freqs[i + 1]
        for (let j = len - 1; j > i + 1; j--) {
            const cutMe = freqs[j]
            const reduceTo = leftFreq + k
            outcome += Math.max(0, cutMe - reduceTo)
        }

        result = Math.min(result, outcome)
    }
    

    return result
};
```
['JavaScript']