#3016

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Minimum Number of Pushes to Type Word II

Given a word, find the minimum number of pushes to type it on a remapped keypad using a greedy approach.

hash table string greedy sorting counting

Problem Statement

You are given a string 'word' consisting of lowercase English letters. You need to type the word on a remapped telephone keypad where each key is mapped to a distinct collection of letters. The number of pushes required to type a letter depends on its position on the key, and each key can have any number of letters but must map each letter to exactly one key.

The goal is to determine the minimum number of pushes required to type the word on the remapped keypad. You must find a way to remap the keys such that the total number of pushes is minimized, leveraging the greedy approach to assign letters with a higher frequency to keys with fewer pushes.

Examples

Example 1

Input: word = "abcde"

Output: 5

The remapped keypad given in the image provides the minimum cost. "a" -> one push on key 2 "b" -> one push on key 3 "c" -> one push on key 4 "d" -> one push on key 5 "e" -> one push on key 6 Total cost is 1 + 1 + 1 + 1 + 1 = 5. It can be shown that no other mapping can provide a lower cost.

Example 2

Input: word = "xyzxyzxyzxyz"

Output: 12

The remapped keypad given in the image provides the minimum cost. "x" -> one push on key 2 "y" -> one push on key 3 "z" -> one push on key 4 Total cost is 1 * 4 + 1 * 4 + 1 * 4 = 12 It can be shown that no other mapping can provide a lower cost. Note that the key 9 is not mapped to any letter: it is not necessary to map letters to every key, but to map all the letters.

Example 3

Input: word = "aabbccddeeffgghhiiiiii"

Output: 24

The remapped keypad given in the image provides the minimum cost. "a" -> one push on key 2 "b" -> one push on key 3 "c" -> one push on key 4 "d" -> one push on key 5 "e" -> one push on key 6 "f" -> one push on key 7 "g" -> one push on key 8 "h" -> two pushes on key 9 "i" -> one push on key 9 Total cost is 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 2 * 2 + 6 * 1 = 24. It can be shown that no other mapping can provide a lower cost.

Constraints

1 <= word.length <= 105
word consists of lowercase English letters.

Solution Approach

Greedy Mapping of Letters

The problem can be solved by first determining the frequency of each letter in the word. We then assign the most frequent letters to keys with fewer presses. The keypad has 8 keys, with the first 8 keys each mapped to 1, 2, 3, and so on pushes. This mapping minimizes the total number of pushes by ensuring the least costly keys are used most often.

Invariant Validation

After determining the mapping, it’s crucial to validate that the solution adheres to the constraints of the problem. For each letter, its cost is based on how many presses it takes to type it, which is directly linked to its position on the key. This ensures that the greedy choice is valid and results in the minimum possible total cost.

Efficient Computation

Given the constraints, the problem can be solved in O(n) time where n is the length of the word. The approach involves counting letter frequencies and applying a greedy strategy to minimize the number of key presses, ensuring a time complexity of O(n) and space complexity of O(1).

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

The algorithm runs in linear time, O(n), where n is the length of the input word. This is because the solution involves counting the frequency of letters and performing a constant number of operations for each letter. Space complexity is O(1) as the space required does not depend on the input size, apart from the fixed set of key mappings.

What Interviewers Usually Probe

The candidate demonstrates an understanding of greedy algorithms and is able to explain the trade-offs of greedy choices.
The candidate efficiently identifies the mapping strategy and can explain why certain letters should be grouped with fewer presses.
The candidate handles the edge cases well, including cases with repetitive characters or the largest possible word length.

Common Pitfalls or Variants

Common pitfalls

Failing to correctly count the frequency of letters, leading to incorrect mappings.
Misunderstanding how to distribute letters across keys, which can result in suboptimal mappings.
Not recognizing that keys can be left unmapped, potentially overcomplicating the solution.

Follow-up variants

Implementing the solution for a fixed set of key mappings instead of remapping the keys.
Applying the greedy approach to a keypad with a different number of keys.
Adapting the problem to work with uppercase letters or other alphabets.

FAQ

How can I approach the greedy choice in this problem?

The greedy approach works by assigning the most frequent letters to keys that require the least number of presses. This minimizes the total key presses needed to type the word.

What is the key takeaway from solving this problem?

The main takeaway is applying a greedy strategy to efficiently assign letters to keys while minimizing the total number of presses needed.

How do I handle edge cases in this problem?

Edge cases like repetitive characters or extremely large inputs should be handled by ensuring the letter frequency is counted correctly and that no key is unnecessarily mapped.

How is the greedy approach validated in this problem?

The greedy approach is validated by ensuring the mapping of frequent letters to the least costly keys and confirming that the total cost is minimized.

What are the space and time complexities of this problem?

The solution has a time complexity of O(n) and a space complexity of O(1), making it efficient for large inputs.

terminal

Solution

Solution 1: Greedy Algorithm + Sorting

We use a hash table or array $cnt$ to count the number of occurrences of each letter in the string $word$. Next, we sort the letters in descending order of their counts, and then group every $8$ letters together, assigning each group to the $8$ keys.

1

2

3

4

5

6

7

class Solution:
    def minimumPushes(self, word: str) -> int:
        cnt = Counter(word)
        ans = 0
        for i, x in enumerate(sorted(cnt.values(), reverse=True)):
            ans += (i // 8 + 1) * x
        return ans

Continue Practicing

#3035 maximum palindromes after operations #3081 replace question marks in string to minimize its value #3085 minimum deletions to make string k special