# Minimum Number of Pushes to Type Word I
**Difficulty:** EASY
[External](https://leetcode.com/problems/minimum-number-of-pushes-to-type-word-i)
Canonical: https://scaleengineer.com/dsa/problems/minimum-number-of-pushes-to-type-word-i
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** String
---
## Problem
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.

![](https://assets.glich.co/dsa/minimum-number-of-pushes-to-type-word-i/image0.png) 

**Example 1:**

![](https://assets.glich.co/dsa/minimum-number-of-pushes-to-type-word-i/image1.png) 

**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:**

![](https://assets.glich.co/dsa/minimum-number-of-pushes-to-type-word-i/image2.png) 

**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 <= 26`
* `word` consists of lowercase English letters.
* All letters in `word` are distinct.

# Approaches
## Iterative Calculation
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.
**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.
**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 `n` times, where `n` is the word length.
### Explanation
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`.

```java
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;
    }
}
```
### Algorithm
- Initialize a variable `totalPushes` to 0.
- Get the length of the word, `n`.
- Loop with an index `i` from 0 to `n-1`.
- Inside the loop, the cost for the character at index `i` is determined by which tier of slots it falls into. This can be calculated using integer division: `cost = (i / 8) + 1`.
- Add the calculated `cost` to `totalPushes`.
- After the loop finishes, return `totalPushes`.

## Mathematical Grouping
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- Initialize `totalPushes = 0`, `cost = 1`, and `remainingChars = word.length()`.
- While `remainingChars` is 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 `remainingChars` by `count`.
  - Increment `cost` by 1 for the next tier.
- After the loop, return `totalPushes`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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 ans
```