3014. Minimum Number of Pushes to Type Word I

Problem Description

In this problem, you are given a string word that has distinct lowercase English letters. Imagine you have a telephone keypad where each key can be used to type certain letters. Normally, keys 2 to 9 are associated with letters such as key 2 with 'a', 'b', 'c', key 3 with 'd', 'e', 'f', and so on. To type a letter, you need to press a key certain times. For example, to type 'b', you press key 2 twice.

However, in this scenario, you have the ability to remap these keys, meaning you can assign any collection of letters to any key, given that each letter is mapped to exactly one key. Your objective is to find a mapping that allows you to type the given word with the fewest number of key presses.

You need to return the minimum number of key presses required to type the string word after optimally remapping the keys.

Intuition

To solve this problem, we can use a greedy algorithm. Since all letters in the word are distinct and we can remap keys in any way we want, the most efficient approach is to distribute the letters across the keys as evenly as possible. Why? Because this ensures that we use the minimum number of presses per key.

With 8 keys available (keys 2 to 9), the first key will be pressed once for its first letter, twice for its second letter, and so on. By distributing letters evenly, we're minimizing the maximum number of presses for any key.

If the word is shorter than or equal to 8 letters, it can be mapped in such a way that each letter is assigned to a different key, and each key is pressed only once. If the word is longer, we put 8 letters on the first 8 keys; for the next 8 letters, we would need to press each key twice, and so forth. This way, the minimum number of total presses is achieved.

The provided solution calculates the number of presses by adding 8 presses for each complete set of 8 letters and then adding the remaining letters multiplied by the number of letter sets plus one.

Learn more about Greedy and Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Solution Approach

The solution provided does not require any complex data structures or advanced patterns due to the simplicity of its greedy algorithm. It focuses on the fact that all letters in the word are unique and can hence be distributed evenly across the 8 keys available.

The algorithm iterates through the string word and calculates the number of times keys need to be pressed in groups of 8 letters. To explain in greater detail:

The variable ans starts at 0 and is used to accumulate the total number of key presses.
The variable k represents the sequence index within the keys; that is, for the first set of up to 8 letters, k is 1, as each key only needs to be pressed once. For the next set of 8 letters (if there are more than 8 unique letters), k would be 2, because we need to press each key twice to access the second letter in each key, and so on.
The for-loop runs for the count of full groups of 8 letters (n // 8) in the word. For each group, it adds to ans the product of k (the current group index) and 8 (the number of letters in the group). Then it increments k to represent the next sequence for the next group of letters.
After processing all full groups of 8, there might be some leftover letters (less than 8). The algorithm adds to the ans the number of leftovers (n % 8) multiplied by the current k value.
Finally, the calculated ans value, which represents the total number of key presses, is returned.

To illustrate with an example, if word is abcdefghijklmnop, the first 8 letters (abcdefgh) would require one press each (total of 8 presses). The next 8 letters (ijklmnop) are the second set and would require two presses each (total of 2 * 8 = 16 presses). So the solution would be 8 + 16 = 24 presses in total.

This completes the explanation of the solution's implementation. It's a straightforward calculation that relies on the rules of evenly distributing unique letters over a fixed number of keys and optimizing for the fewest total presses.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which technique can we use to find the middle of a linked list?

Fast-slow pointersTwo pointers moving in opposite directionBinary searchDepth first search

I don’t know

Example Walkthrough

Let's go through a sample problem to illustrate the solution approach using the word: program.

In this scenario, the word program has 7 unique letters. According to the rules of the telephone keypad, we want to remap these letters to minimize the number of key presses.

Since we have 8 keys (2 to 9) and only 7 unique letters, we can assign each letter to a different key because the number of letters is less than or equal to the number of keys. Here is how we can remap the letters:

Key 2: 'p' (1 press)
Key 3: 'r' (1 press)
Key 4: 'o' (1 press)
Key 5: 'g' (1 press)
Key 6: 'r' (1 press)
Key 7: 'a' (1 press)
Key 8: 'm' (1 press)

Since each letter is assigned to its own key, we only need to press each key once to type the word program. This means we only need a total of 7 presses - one press for each letter.

To summarize the steps in the algorithm:

We initialize ans to 0.
We note that k = 1 because we have not yet exceeded 8 unique letters.
There are no full groups of 8, so the for-loop does not add anything to ans.
We then calculate the number of leftover letters, which is 7 % 8 = 7, multiply by k (which is 1), and add the result to ans.
Finally, we have ans = 0 + 7*1 = 7. Therefore, the minimum number of key presses required is 7.

This simple example shows how the provided solution uses the rules of a remappable keypad and a greedy distribution of letters to keys to minimize the number of key presses required to type the word.

Solution Implementation

1class Solution:
2    def minimumPushes(self, word: str) -> int:
3        # Calculate the length of the word
4        word_length = len(word)
5        # Initialize 'total_pushes' to store the total pushes required
6        # Initialize 'pushes_per_batch' which represents the number of pushes for each batch of 8 characters
7        total_pushes, pushes_per_batch = 0, 1
8      
9        # Process all complete batches of 8 characters
10        for _ in range(word_length // 8):
11            total_pushes += pushes_per_batch * 8  # Add the pushes required for a batch of 8 characters
12            pushes_per_batch += 1  # Increment the number of pushes needed for each subsequent batch
13      
14        # Add the pushes required for the remaining characters, if any
15        total_pushes += pushes_per_batch * (word_length % 8)
16      
17        # Return the total number of pushes required
18        return total_pushes
19

1class Solution {
2    public int minimumPushes(String word) {
3        int wordLength = word.length(); // Length of the string word
4        int totalPushes = 0; // Total number of pushes required
5        int pushMultiplier = 1; // Multiplier for each group of 8 characters
6
7        // Loop through the groups of 8 characters in the word
8        for (int i = 0; i < wordLength / 8; ++i) {
9            totalPushes += pushMultiplier * 8; // Add pushes for this group
10            ++pushMultiplier; // Increment the multiplier for the next group
11        }
12
13        // Add pushes for the remaining characters (if any)
14        totalPushes += pushMultiplier * (wordLength % 8);
15
16        return totalPushes; // Return the total number of pushes
17    }
18}
19

1class Solution {
2public:
3    // Function to calculate the minimum number of pushes needed
4    int minimumPushes(string word) {
5        int length = word.size();  // Get the length of the input string
6        int answer = 0;            // Initialize the answer to zero
7        int multiplier = 1;        // Initialize the multiplier to one
8
9        // Process complete sets of 8 characters
10        for (int i = 0; i < length / 8; ++i) {
11            answer += multiplier * 8;  // Add 8 times the current multiplier to the answer
12            ++multiplier;              // Increment the multiplier for the next set
13        }
14
15        // Add the remaining characters (less than 8 if any)
16        answer += multiplier * (length % 8);
17
18        // Return the total minimum pushes calculated
19        return answer;
20    }
21};
22

1/**
2 * Calculate the minimum number of pushes required based on the "word" string's length.
3 * Each set of 8 characters requires an increasing number of pushes.
4 *
5 * @param {string} word - The string to be analyzed for push calculations.
6 * @return {number} - The minimum number of pushes required.
7 */
8function minimumPushes(word: string): number {
9    // Get the length of the input string.
10    const wordLength = word.length;
11    // Initialize the answer to be returned with 0.
12    let totalPushes = 0;
13    // Start with k = 1, which will be multiplied with the character count.
14    let multiplier = 1;
15  
16    // Loop through the string 8 characters at a time.
17    for (let i = 0; i < (wordLength / 8) | 0; ++i) {
18        totalPushes += multiplier * 8; // Add 8 times the current multiplier to the total.
19        ++multiplier; // Increment the multiplier for the next set of characters.
20    }
21  
22    // Add the remaining characters multiplied by the current multiplier
23    // for the case where word length is not a multiple of 8.
24    totalPushes += multiplier * (wordLength % 8);
25  
26    // Return the total number of pushes calculated.
27    return totalPushes;
28}
29

Not Sure What to Study? Take the 2-min Quiz：

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

O(1)O(log n)O(sqrt(n))O(n)

I don’t know

Time and Space Complexity

The time complexity of the given code is O(1), also described as constant time complexity. The reason for this is that the loop runs a fixed number of times that depends on the length of the string word divided by 8. Since division is a constant-time operation, and the loop consequently runs a constant number of iterations (specifically, n // 8 times), the complexity does not grow with the size of the input but remains capped. The modifications inside the loop are also constant-time operations, resulting in an overall constant time complexity.

The space complexity of the code is O(1), meaning it requires a constant amount of additional space that does not grow with the size of the input. This is because the variables n, ans, k, and _ each occupy a fixed amount of space, and no additional space that scales with the input size (word) is required or allocated during the execution of the code.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

3014. Minimum Number of Pushes to Type Word I

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Recommended Readings