[Rust] Beats 100% -- it's not O(n^2) if you only have 26 letters
Intuition\nFirst thing, we need to count the number of frequency of each letter in word, and sort them so we can easily identify low frequencies and high freque
# Intuition\nFirst thing, we need to count the number of frequency of each letter in word, and sort them so we can easily identify low frequencies and high frequencies.\n\nThen, when faced with a frequency distribution, we have two approaches to reduce it down to some range.\n\nOne option would be to keep the lowest-frequency letter as it is, and then reduce all frequencies that are too high down until they fit. For example, if our frequency array was [99, 99, 101] with k = 1, we could achieve this in one step by reducing 101 -> 100, because 99 + 1 == 100.\n\nThe other option is to drop the lowest-frequency letter entirely, and then repeat on the inner array. For example, if our frequency array is [1, 99, 101] with k =1 then it\'s best to drop the 1 to get [99, 101] and then reduce from 101 -> 100, getting to [99, 100] in two moves.\n\nBecause there are at most 26 letters in consideration, we can easily test all possibilities of number of dropped letters; no dropped letters, drop the lowest-frequency, drop the two lowest-frequency, etc. until we get to a point where the cost of dropping the (x) lowest letters exceeds the best-tested result so far.\n\n# Approach\nStore frequencies a byte array; this is stack-allocated, finite memory.\n\nThen take a slice into that memory of just the portion with positive probabilities to avoid unnecessary iterations, and incrementally reduce the slice window.\n\nKeep two running totals; the best total cost seen so far, and the cost of dropping the lowest-frequencey frequencies to get to the current frequencies slice. Early-exit once the drop cost would exceed the best-achieved cost.\n\n# Complexity\n- Time complexity: O(n) to scan the original word. After that, even in the worst case (for a word with all 26 letters that needs to drop 25 of them) we perform finitely many operations. If the \n\n- Space complexity: O(1), we only need a 26-size array and a few integers as working memory.\n\n# Code\n```\nimpl Solution {\n    pub fn minimum_deletions(word: String, k: i32) -> i32 {\n        let mut freqs = [0_i32; 26];\n        for byte in word.bytes() {\n            freqs[(byte-b\'a\') as usize] += 1;\n        }\n        freqs.sort_unstable();\n        let left = {\n            let mut left = 0;\n            while left < 26 && freqs[left] == 0 {\n                left += 1;\n            }\n            left\n        };\n        let mut freqs = &freqs[left..];\n\n        let mut best = i32::MAX;\n        let mut drop_cost = 0;\n        while let Some(&lowest) = freqs.first() {\n            let keep_lowest: i32 = freqs.iter().filter_map(|&freq| if lowest + k < freq {\n                Some(freq - lowest - k)\n            } else {\n                None\n            }).sum();\n            best = best.min(drop_cost + keep_lowest);\n            drop_cost += lowest;\n            if drop_cost >= best {\n                return best;\n            }\n            freqs = &freqs[1..];\n        }\n\n        // This will only be reached if word is empty,\n        // or contains chars other than [a-z]\n        0\n    }\n}\n```
['Rust']