Show problems as
Classic problem #1320HardStringDynamic Programming

Minimum Distance to Type a Word Using Two Fingers

Real-world version: Two Hands On A Lettered Key Panel
Tracked in this browser only
Read Minimum Distance to Type a Word Using Two Fingers on LeetCode(opens in a new tab)

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

A dispatcher enters a call sign on a panel of lettered keys using two hands.

The panel carries 26 keys, one per uppercase letter, laid out in a rectangle four columns wide and filled in alphabetical order, left to right and then top to bottom. Write t for a letter's place in the alphabet counted from zero, so A is 0 and Z is 25. That letter's key sits in row t / 4 (integer division) and column t % 4. Row 0 therefore holds A B C D, row 1 holds E F G H, and the bottom row 6 holds only Y and Z.

Moving a hand from one key to another costs the number of rows between them plus the number of columns between them.

The letters of call must be pressed in order. Before each press the dispatcher picks which of the two hands makes it; that hand travels from the key it is resting on to the key being pressed and the travel cost is added to the running total. Both hands begin away from the panel, so the first press made by a hand costs nothing. A hand then rests on the key it pressed until it is used again, and the two hands are allowed to rest on the same key.

Return the smallest total travel cost for entering the whole call sign.

Examples

Example 1

Input
call = "MAP"
Output
3

One hand presses M at row 3 column 0, the other hand presses A at row 0 column 0 for nothing since it is that hand's first press, and then the first hand slides from M to P at row 3 column 3, three columns across.

Example 2

Input
call = "ZEBRA"
Output
5

One hand can take Z at row 6 column 1 and later R at row 4 column 1, travelling two rows. The other hand takes E at row 1 column 0 free of charge, then B at row 0 column 1 for two steps, then A at row 0 column 0 for one more, which totals 5.

Example 3

Input
call = "KKKKKK"
Output
0

Every press is on the same key, so a single hand can stay put and travel nothing.

Constraints

  • 1 <= call.length <= 300
  • call consists of uppercase English letters only.

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 min_hand_travel(call: str) -> int:
Java
public int minHandTravel(String call)

More on the same topics