0513EasyMathStringGreedy

Eight-Key Field Terminal

Tracked in this browser only

Trains the technique from

LeetCode 3014Minimum Number of Pushes to Type Word I

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def fewest_presses(word: str) -> int:

Java

public int fewestPresses(String word)

The intended approach

Time O(L) where L is the length of word.Space O(1): one running total.

Across the whole keypad there are eight slots that cost one press, eight that cost two, and so on, and since every letter of `word` is typed exactly once only the multiset of slot costs matters. Filling the cheapest slots first therefore charges the i-th letter `i // 8 + 1` presses, and the answer is that sum. The letters themselves never enter the arithmetic, only how many of them there are.

Pythonentry point: fewest_presses

def fewest_presses(word):
    # Eight keys are available, so the eight cheapest slots across the keypad all
    # cost one press, the next eight cost two presses, and so on. Handing the
    # letters out in that order gives the i-th letter a cost of i // 8 + 1.
    # O(L) time, O(1) space.
    total = 0
    for i in range(len(word)):
        total += i // 8 + 1
    return total

The obvious version

Treat it as splitting the letters across the eight keys. A key loaded with `take` letters costs `take * (take + 1) / 2` presses, so run a table over keys used and letters placed, trying every count for the next key, and read off the cheapest way to place all the letters.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_fewest_presses(word):
    letters = len(word)
    INF = float("inf")
    best = [INF] * (letters + 1)
    best[0] = 0
    for _key in range(8):
        nxt = [INF] * (letters + 1)
        for placed in range(letters + 1):
            if best[placed] == INF:
                continue
            for take in range(letters - placed + 1):
                cost = take * (take + 1) // 2
                if best[placed] + cost < nxt[placed + take]:
                    nxt[placed + take] = best[placed] + cost
        best = nxt
    return best[letters]

How this problem was checked

Reference solution executed against 11 test cases — 11 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in