Minimum Number of Pushes to Type Word I
EasyPrompt
You are given a string word containing distinct 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. For example, the key 2 is mapped with ["a","b","c"], we need to push the key one time to type "a", two times to type "b", and three times to type "c" .
It is allowed to remap the keys numbered 2 to 9 to distinct collections of letters. The keys can be remapped to any amount of letters, but each letter must be mapped to exactly one key. You need to find the minimum number of times the keys will be pushed to type the string word.
Return the minimum number of pushes needed to type word after remapping the keys.
An example mapping of letters to keys on a telephone keypad is given below. Note that 1, *, #, and 0 do not map to any letters.
Example 1:
Input: word = "abcde"
Output: 5
Explanation: 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 = "xycdefghij"
Output: 12
Explanation: The remapped keypad given in the image provides the minimum cost.
"x" -> one push on key 2
"y" -> two pushes on key 2
"c" -> one push on key 3
"d" -> two pushes on key 3
"e" -> one push on key 4
"f" -> one push on key 5
"g" -> one push on key 6
"h" -> one push on key 7
"i" -> one push on key 8
"j" -> one push on key 9
Total cost is 1 + 2 + 1 + 2 + 1 + 1 + 1 + 1 + 1 + 1 = 12.
It can be shown that no other mapping can provide a lower cost.
Constraints:
1 <= word.length <= 26wordconsists of lowercase English letters.- All letters in
wordare distinct.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach simulates the process of assigning each character of the word to a key one by one. We iterate through the characters and assign them to the cheapest available slots on the keypad. The cost of a push depends on how many characters are already on a key. To minimize the total pushes, we fill up all the "1-push" slots first, then all the "2-push" slots, and so on.
Algorithm
- Initialize a variable
totalPushesto 0. - Get the length of the word,
n. - Loop with an index
ifrom 0 ton-1. - Inside the loop, the cost for the character at index
iis determined by which tier of slots it falls into. This can be calculated using integer division:cost = (i / 8) + 1. - Add the calculated
costtototalPushes. - After the loop finishes, return
totalPushes.
Walkthrough
The core idea is that since all characters in the word are distinct and must be typed once, it doesn't matter which specific character goes where, only the number of pushes required for each position. The optimal strategy is to fill the cheapest slots first.
The cheapest positions are the first slots on each of the 8 available keys (keys 2-9). These cost 1 push each. The next cheapest are the second slots on each key, costing 2 pushes each. This pattern continues for the third (3 pushes) and fourth (4 pushes) slots.
We can iterate from i = 0 to word.length() - 1. The index i represents the i-th character we are assigning (in any order). The cost for the character at index i is determined by which "tier" of slots it falls into. For example:
- Characters at indices 0-7 fall into the 1-push tier.
- Characters at indices 8-15 fall into the 2-push tier.
- and so on.
This logic can be simplified to a formula cost = (i / 8) + 1 for the character at index i.
class Solution { public int minimumPushes(String word) { int n = word.length(); int totalPushes = 0; for (int i = 0; i < n; i++) { // The cost is 1 for the first 8 chars, 2 for the next 8, and so on. // This can be calculated as (i / 8) + 1. int cost = (i / 8) + 1; totalPushes += cost; } return totalPushes; }}Complexity
Time
O(n), where `n` is the length of the `word`. The loop runs `n` times, performing a constant amount of work in each iteration.
Space
O(1), as we only use a few variables for calculation, regardless of the input size.
Trade-offs
Pros
Simple to understand and implement.
Directly models the greedy assignment strategy in a clear, step-by-step manner.
Cons
Slightly less efficient than a direct mathematical approach, as it involves a loop that runs
ntimes, wherenis the word length.
This approach optimizes the iterative calculation by processing characters in groups rather than one by one. We observe that characters can be bundled into groups of 8, with each character in a bundle having the same push cost. This allows for a direct mathematical calculation in a loop that runs a constant number of times, making it highly efficient.
Algorithm
- Initialize
totalPushes = 0,cost = 1, andremainingChars = word.length(). - While
remainingCharsis greater than 0:- Determine the number of characters to assign in the current cost tier:
count = min(remainingChars, 8). - Add the pushes for this group to the total:
totalPushes += count * cost. - Decrease
remainingCharsbycount. - Increment
costby 1 for the next tier.
- Determine the number of characters to assign in the current cost tier:
- After the loop, return
totalPushes.
Walkthrough
The underlying greedy strategy is the same: fill the cheapest slots first. The first 8 characters cost 1 push each, the next 8 cost 2 pushes each, and so on.
Instead of a loop over each character, we can process the word in chunks of 8. We repeatedly take up to 8 characters from the word, assign them to the current cost tier, add the total pushes for this chunk to our result, and then move to the next cost tier.
For example, for a word of length 10, we first take a chunk of 8 characters. They all cost 1 push, contributing 8 * 1 = 8 to the total. We are left with 2 characters. These fall into the next tier, costing 2 pushes each, contributing 2 * 2 = 4. The total is 8 + 4 = 12.
This can be implemented with a simple while loop that runs at most 4 times, since the word length is at most 26.
class Solution { public int minimumPushes(String word) { int n = word.length(); int pushes = 0; int cost = 1; int charsPerTier = 8; while (n > 0) { int countInTier = Math.min(n, charsPerTier); pushes += countInTier * cost; n -= countInTier; cost++; } return pushes; }}Complexity
Time
O(1). The number of calculations is constant regardless of the input size `n`. The `while` loop runs at most 4 times due to the constraint `n <= 26`.
Space
O(1). Only a few variables are used for calculation.
Trade-offs
Pros
Most efficient approach with constant time complexity.
Concise and requires minimal computation, making it very fast.
Cons
The logic might be slightly less direct to grasp for a beginner compared to iterating through each character individually.
Solutions
Solution
class Solution {public int minimumPushes(String word) { int n = word.length(); int ans = 0, k = 1; for (int i = 0; i < n / 8; ++i) { ans += k * 8; ++k; } ans += k * (n % 8); return ans; }}class Solution {public: int minimumPushes(string word) { int n = word.size(); int ans = 0, k = 1; for (int i = 0; i < n / 8; ++i) { ans += k * 8; ++k; } ans += k * (n % 8); return ans; }};class Solution : def minimumPushes ( self , word : str ) -> int : n = len ( word ) ans , k = 0 , 1 for _ in range ( n // 8 ): ans += k * 8 k += 1 ans += k * ( n % 8 ) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.