> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Minimum Number of Pushes to Type Word II

> Tested Python solution for LeetCode 3016 with 16 pytest cases. Generate a practice environment with lcpy.

LeetCode 3016, [Medium](/catalog/medium). Topics: [Hash Table](/catalog/topics/hash-table), [String](/catalog/topics/string), [Greedy](/catalog/topics/greedy), [Sorting](/catalog/topics/sorting), [Counting](/catalog/topics/counting). [View on LeetCode](https://leetcode.com/problems/minimum-number-of-pushes-to-type-word-ii/description/).

Generate this problem as a practice environment: tested reference solution, 16 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 3016   # by problem number
lcpy gen -s minimum_number_of_pushes_to_type_word_ii   # by problem name
```

## Problem

You are given a string `word` containing 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.

![Keypad](https://assets.leetcode.com/uploads/2023/12/26/keypaddesc.png)

### Examples

![Example 1](https://assets.leetcode.com/uploads/2023/12/26/keypadv1e1.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.leetcode.com/uploads/2024/08/20/edited.png)

```
Input: word = "xyzxyzxyzxyz"
Output: 12
Explanation: 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](https://assets.leetcode.com/uploads/2023/12/27/keypadv2.png)

```
Input: word = "aabbccddeeffgghhiiiiii"
Output: 24
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
"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 <= 10^5`
* `word` consists of lowercase English letters.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/minimum_number_of_pushes_to_type_word_ii/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/minimum_number_of_pushes_to_type_word_ii/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
from collections import Counter


class Solution:
    # Time: O(n)
    # Space: O(1)
    def minimum_pushes(self, word: str) -> int:
        counts = sorted(Counter(word).values(), reverse=True)
        return sum(count * (index // 8 + 1) for index, count in enumerate(counts))
```

## Complexity

| Time | Space |
| - | - |
| O(n) | O(1) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.