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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Number of Pushes to Type Word II

Difficulty: Medium

Problem Description

You are given a string word containing lowercase English letters. Telephone keypads have keys mapped with distinct collections of lowercase English letters, which can be used to form words by pushing them. You need to find the minimum number of times the keys will be pushed to type the string word after remapping the keys.

Key Insights

  • Each letter can be mapped to any key from 2 to 9.
  • Each key can have a distinct collection of letters.
  • The cost to type a letter is determined by its position on the key (1 push for the first letter, 2 for the second, etc.).
  • To minimize the total pushes, letters should be distributed based on their frequency in the input word.

Space and Time Complexity

Time Complexity: O(n log n) where n is the length of the word (due to sorting). Space Complexity: O(1) if we ignore the input and output space, or O(26) for the frequency count of letters.

Solution

To solve the problem, we can follow these steps:

  1. Count the frequency of each letter in the input string using a hash table.
  2. Sort the frequencies in descending order.
  3. Distribute the letters across the keys such that the most frequently occurring letters are assigned to the keys with the least push cost.
  4. Calculate the total number of pushes based on the distribution.

The data structures used are a hash table (for counting frequencies) and an array (for sorting frequencies).

Code Solutions

from collections import Counter

def min_pushes(word):
    freq = Counter(word)  # Count frequency of each letter
    counts = sorted(freq.values(), reverse=True)  # Sort frequencies in descending order
    pushes = 0
    
    for i, count in enumerate(counts):
        pushes += count * ((i // 3) + 1)  # Push cost is determined by the key position (1-based)
    
    return pushes
← Back to All Questions