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 Keypresses

Number: 2405

Difficulty: Medium

Paid? Yes

Companies: Amazon

Problem Description

You are given a keypad with 9 buttons (numbered 1 to 9). Each button can be mapped to up to 3 lowercase English characters, and every letter from 'a' to 'z' must be assigned to exactly one button (thus, one button might have 1, 2, or 3 letters in a fixed order). Typing the first letter assigned to a button requires a single keypress, the second requires two keypresses, and the third requires three keypresses. Given a string s, determine the minimum total number of keypresses required to type s assuming you can optimally assign the letters to the buttons subject to the given constraints.

Key Insights

  • To minimize total keypresses, assign the most frequently used characters to positions that require the fewest keypresses.
  • Count the frequency of each character in s.
  • Sort the frequencies in descending order.
  • Given there are 9 buttons with up to 3 characters per button (27 possible positions) and since we only need 26 letters, assign the top 9 most frequent characters to the first positions (1 press), the next 9 to the second positions (2 presses), and the remaining to the third positions (3 presses).
  • The total cost is computed by summing frequency * assigned number of keypresses for each character.

Space and Time Complexity

Time Complexity: O(n + k log k), where n is the length of s and k is 26 (the number of letters), so effectively O(n). Space Complexity: O(1) (or O(26) for the frequency count, which is constant).

Solution

We first count how many times each letter appears in the string s. With this information, we sort these counts in descending order. The idea is to assign higher frequency letters to positions that require fewer keypresses. Since there are 9 first positions, 9 second positions, and the remaining in third positions within the 9 buttons, we can calculate the number of keypresses for a letter assigned at sorted index i by (i // 9 + 1). Multiply the frequency by the number of presses needed and sum the results.

Code Solutions

# Python solution for Minimum Number of Keypresses

def minimumKeypresses(s: str) -> int:
    # Count frequency of each character using a dictionary
    freq = {}
    for char in s:
        freq[char] = freq.get(char, 0) + 1

    # Collect frequencies in a list and sort them in descending order
    frequencies = sorted(freq.values(), reverse=True)

    total_keypresses = 0
    for i, count in enumerate(frequencies):
        # Determine the number of keypresses by using integer division by 9,
        # since there are 9 first-press positions, then 9 second-press, etc.
        presses = (i // 9) + 1
        total_keypresses += count * presses
    return total_keypresses

# Example usage:
# s = "apple"
# print(minimumKeypresses(s))  # Expected output: 5
← Back to All Questions