unreasonably effective

you can be sloppy, as long as you are rigorous

LeetCode 3016: Minimum Number of Pushes to Type Word II

link

The more frequent a character is, the earlier in the mapping it should appear. There are only eight keys that can have character mapping. So, we keep assigning groups of eight characters to the eight keys in decreasing order of frequency.

Say there are n characters that need mapping with m of them distinct.

Time: \mathcal{O}(n + m \cdot \lg{m}), space: \mathcal{O}(m).

class Solution:
    def minimumPushes(self, word: str) -> int:
        count_of = {}
        for c in word:
            count_of[c] = count_of.get(c, 0) + 1

        total_push_count = 0
        char_push_count = 1
        for i, k in enumerate(sorted(count_of.values(), reverse=True), start=1):
            total_push_count += k * char_push_count

            char_push_count += 1 if i % 8 == 0 else 0

        return total_push_count

tanvirdotzaman

,

Leave a comment