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 I

Number: 3275

Difficulty: Easy

Paid? No

Companies: Amazon, Google

Problem Description

Given a string word of distinct lowercase letters, remap the keys (from 2 to 9) of a telephone keypad into arbitrary groups such that each letter is assigned to exactly one key. The cost to type a letter is determined by its position on the key (1-indexed). The goal is to minimize the total number of key presses required to type the word.

Key Insights

  • Since all letters are distinct and each letter occurs exactly once, frequency does not affect the assignment.
  • There are 8 available keys (numbers 2 to 9). The optimal strategy is to assign as many letters as possible to the first position (cost = 1) on each key.
  • If more than 8 letters are present, the additional letters must be assigned as the second letter on keys (cost = 2), then third (cost = 3), and so on.
  • The total cost for the word is the sum of (1 + the number of full rounds of 8 letters before it) for each letter.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the word. Space Complexity: O(1), using a constant amount of extra space.

Solution

The solution works by iterating over each letter in the given word and calculating the cost based on its position in an optimal assignment. Since there are 8 keys, the first 8 letters cost 1 each, the next 8 cost 2 each, and so on. This is computed by using integer division (i // 8) for each letter's index to determine its cost multiplier. Data structures used are simple counters and loops, making the solution both efficient and straightforward.

Code Solutions

# Python solution with detailed comments
def minimumPushes(word):
    total_cost = 0  # Initialize total cost of key pushes
    n = len(word)  # Number of letters in the word
    # Iterate through each letter by index
    for i in range(n):
        # For each letter, calculate the cost based on its position:
        # Letters in positions 0 to 7 cost 1 push, 8 to 15 cost 2 pushes, etc.
        cost = (i // 8) + 1
        total_cost += cost  # Add the cost for this letter to total
    return total_cost

# Example usage
print(minimumPushes("abcde"))       # Expected output: 5
print(minimumPushes("xycdefghij"))  # Expected output: 12
← Back to All Questions