We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Number of Pushes to Type Word II

Number: 3276

Difficulty: Medium

Paid? No

Companies: Amazon, DE Shaw

Problem Description

Given a word composed of lowercase English letters, remap the telephone keypad keys 2 to 9 (each mapping to a distinct collection of letters) in any way such that every letter is assigned to exactly one key. When a letter is mapped to a key, its cost is determined by its position in that key’s mapping (first letter costs 1 push, second costs 2 pushes, and so on). The goal is to minimize the total number of key pushes required to type the given word.

Key Insights

  • The problem reduces to assigning each letter an effective cost based on its frequency in the word.
  • Since each key can contain an arbitrary number of letters and there are 8 keys, the optimal strategy is to assign the most frequent letters a cost of 1 push, the next set a cost of 2 pushes, and so on.
  • By sorting the letters by frequency in descending order and then partitioning them into groups of at most 8, the minimum total cost can be computed by summing (frequency * (group index + 1)).

Space and Time Complexity

Time Complexity: O(n + 26 log 26), which is effectively O(n) because the number of letters (26) is constant. Space Complexity: O(26) = O(1) for the frequency counting array.

Solution

The solution employs a greedy algorithm along with frequency counting:

  1. Count the frequency of each letter in the word.
  2. Sort the frequencies in descending order.
  3. Since there are 8 keys, assign the letters according to their sorted order where the j-th group (of up to 8 letters) has a cost of (j+1).
  4. Calculate the total cost by summing frequency * assigned cost for each letter. Data structures used include an array or dictionary (hash table) for frequency counts, and a list or vector for the sorted frequencies.

Code Solutions

def minPushesToTypeWord(word):
    # Count frequency of each letter
    freq = {}
    for ch in word:
        freq[ch] = freq.get(ch, 0) + 1
    # Get the frequencies sorted in descending order
    counts = sorted(freq.values(), reverse=True)
    pushes = 0
    # Each group of 8 letters gets an increasing cost starting from 1
    for i, count in enumerate(counts):
        cost = (i // 8) + 1  # Determine the cost based on the group index
        pushes += count * cost
    return pushes

# Example usage:
print(minPushesToTypeWord("abcde"))               # Expected output: 5
print(minPushesToTypeWord("xyzxyzxyzxyz"))          # Expected output: 12
print(minPushesToTypeWord("aabbccddeeffgghhiiiiii")) # Expected output: 24
← Back to All Questions