Show problems as
Classic problem #3014EasyMathStringGreedy

Minimum Number of Pushes to Type Word I

Real-world version: Eight-Key Field Terminal
Tracked in this browser only
Read Minimum Number of Pushes to Type Word I on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A field terminal has exactly 8 keys set aside for letters. Before a message is typed, a technician loads the keypad: each letter that the message needs is assigned to one of the 8 keys, and the letters landing on a key are put in an order of the technician's choosing. A key may be loaded with as many letters as wanted, and a key may also be left empty, but a letter sits on exactly one key.

Typing a letter that sits in position p of its key's list costs p presses, counting positions from 1. So the first letter on a key costs one press, the second costs two, and so on.

The message is the string word, whose letters are all different, so every letter is typed exactly once. Return the fewest presses needed to type word when the keypad is loaded as well as possible.

Examples

Example 1

Input
word = "qwrtypsd"
Output
8

There are eight letters and eight keys, so every letter can sit first on a key of its own and cost one press.

Example 2

Input
word = "qwrtypsdf"
Output
10

Eight of the nine letters sit first on a key and cost one press each; the remaining letter sits second on some key and costs two presses.

Example 3

Input
word = "qwrtypsdfghjklzx"
Output
24

Eight letters sit first on their key at one press each and the other eight sit second at two presses each, giving 8 + 16 presses.

Constraints

  • 1 <= word.length <= 26
  • word consists of lowercase English letters.
  • All letters in word are different.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def fewest_presses(word: str) -> int:
Java
public int fewestPresses(String word)

More on the same topics