0907MediumHash TableStringGreedySortingCounting

Fewest Presses on a Letter Pad

Tracked in this browser only

Trains the technique from

LeetCode 3016Minimum Number of Pushes to Type Word II

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 pad has eight keys free for letters. Every one of the twenty-six letters is placed on exactly one key, and a key may hold any number of them in any order. A letter placed p-th on its key takes p presses each time it is typed.

Choose the arrangement that makes typing word cost as little as possible, and return that number of presses.

Examples

Example 1

Input: s = "abcdefghi"
Output: 10

Nine distinct letters are typed once each. Eight of them take a first place on the eight keys at one press apiece, and the ninth has to share a key, costing two.

Example 2

Input: s = "aaaaabbbbcccdde"
Output: 15

Only five distinct letters appear, so each gets a key to itself and every press costs one, giving the length of the word.

Example 3

Input: s = "zzzzzzzz"
Output: 8

One letter on its own key costs a single press each time.

Constraints

1 <= word.length <= 10^5
word consists of lowercase English letters only

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 minimum_pushes(word: str) -> int:

Java

public int minimumPushes(String word)

The intended approach

Time O(n + A log A) for a word of length n over an alphabet of size A: one tally then a sort of at most twenty-six counts.Space O(A) for the tally.

Only how often each letter is typed matters, since where a letter sits changes its cost but not anything else's. The costs on offer are fixed: across eight keys there are eight first places costing one press, eight second places costing two, eight third places costing three, and two fourth places costing four. So the job is handing out those costs to the letters, and pairing the most-typed letters with the cheapest places is best: swapping a more-typed letter onto a dearer place than a less-typed one always costs more, so no arrangement beats sorting the counts downward and filling the cheap places first. That makes the letter in sorted position `i`, counting from zero, cost one more than `i` divided by eight, rounded down.

Pythonentry point: minimum_pushes

def minimum_pushes(word):
    tally = {}
    for ch in word:
        tally[ch] = tally.get(ch, 0) + 1
    counts = sorted(tally.values(), reverse=True)
    total = 0
    for i in range(len(counts)):
        total += counts[i] * (i // 8 + 1)
    return total

The obvious version

Hand the costs out by hand instead. Work out how many places of each cost the pad offers, choose how many letters take each cost, and then try every way of matching those costs to the letters, keeping the cheapest total. Makes no argument about which letters deserve the cheap places.

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_minimum_pushes(word):
    import itertools
    tally = {}
    for ch in word:
        tally[ch] = tally.get(ch, 0) + 1
    counts = list(tally.values())
    letters = len(counts)
    places = [8, 8, 8, 2]
    best = [None]

    def pick(at, chosen):
        if at == len(places):
            if sum(chosen) != letters:
                return
            bag = []
            for cost in range(len(places)):
                for _ in range(chosen[cost]):
                    bag.append(cost + 1)
            for order in set(itertools.permutations(bag)):
                total = 0
                for i in range(letters):
                    total += counts[i] * order[i]
                if best[0] is None or total < best[0]:
                    best[0] = total
            return
        top = places[at]
        if top > letters:
            top = letters
        for take in range(top + 1):
            pick(at + 1, chosen + [take])

    pick(0, [])
    return best[0]

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