Problem of The Day: Minimum Number of Pushes to Type Word II

Problem Statement

Intuition

When solving this problem, my first thought was to find an efficient way to distribute characters across different keys such that the total number of pushes required is minimized. Since each key can have multiple characters, my goal was to ensure the characters with the highest frequency are assigned to keys with the least number of characters currently assigned.

Approach

I will use a greedy approach combined with a min-heap to keep track of the number of characters assigned to each key. I will follow these steps:

1. Count the frequency of each character in the input string.
2. Use a min-heap to store the keys and the number of characters assigned to each key.
3. Sort the characters by frequency in descending order.
4. For each character, assign it to the key with the least number of characters currently assigned (the root of the min-heap).
5. Update the total number of pushes required by multiplying the frequency of the character by its position in the key’s character list.
6. Update the min-heap with the new number of characters for that key.

Complexity

• Time complexity: (O(n \log n)), where (n) is the length of the input string. This includes counting the frequency of characters, sorting them, and managing the min-heap.
• Space complexity: (O(k)), where (k) is the number of unique characters in the input string. This is used for storing the character frequencies and the min-heap.

Code

from collections import Counter
import heapq

class Solution:
    def minimumPushes(self, word: str) -> int:
        counter = Counter(word)
        arr = []
        min_heap = [[0, i] for i in range(2, 10)]
        for c, count in counter.items():
            arr.append([count, c])
        map_keys = {i:[] for i in range(2, 10)}
        res = 0
        for count, c in sorted(arr, reverse=True):
            num_of_char, num = heapq.heappop(min_heap)
            num_of_char += 1
            res += (num_of_char * count)
            heapq.heappush(min_heap, [num_of_char, num])
        return res

Editorial

Approach 1: Greedy Sorting

class Solution:
    def minimumPushes(self, word: str) -> int:
        # Frequency list to store count of each letter
        frequency = [0] * 26

        # Count occurrences of each letter
        for c in word:
            frequency[ord(c) - ord("a")] += 1
        # Sort frequencies in descending order
        frequency.sort(reverse=True)

        total_pushes = 0

        # Calculate total number of presses
        for i in range(26):
            if frequency[i] == 0:
                break
            total_pushes += (i // 8 + 1) * frequency[i]

        return total_pushes

• time: O(n)
• space: O(1)

Approach 2: Using Heap

class Solution:
    def minimumPushes(self, word: str) -> int:
        # Frequency map to store count of each letter
        frequency_map = Counter(word)

        # Priority queue to store frequencies in descending order
        frequency_queue = [-freq for freq in frequency_map.values()]
        heapq.heapify(frequency_queue)

        total_pushes = 0
        index = 0

        # Calculate total number of presses
        while frequency_queue:
            total_pushes += (1 + (index // 8)) * (
                -heapq.heappop(frequency_queue)
            )
            index += 1
        return total_pushes

• time: O(n)
• space: O(1)