LeetCode Entry
3016. Minimum Number of Pushes to Type Word II
Minimum keystrokes after assigning letter to keys
3016. Minimum Number of Pushes to Type Word II medium
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/694
Problem TLDR
Minimum keystrokes after assigning letter to keys #medium
Intuition
By intuition we should assign the more frequent letters first.
Approach
We can use some languages’ API, or math (i / 8 + 1).
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(1)\)
Code
fun minimumPushes(word: String) = word
.groupingBy { it }.eachCount()
.values.sortedDescending()
.chunked(8).withIndex()
.sumOf { (i, s) -> (i + 1) * s.sum() }
pub fn minimum_pushes(word: String) -> i32 {
let mut freq = vec![0; 26];
for b in word.bytes() { freq[b as usize - 97] += 1 }
freq.sort_unstable();
(0..26).map(|i| (i as i32 / 8 + 1) * freq[25 - i]).sum()
}