Typing With Two Fingers

Hard

Uppercase English letters sit on a keyboard six to a row: the letter with alphabet index p (A is 0, B is 1, …, Z is 25) is in row p // 6 and column p % 6. For example, A is at (0, 0), H at (1, 1) and Z at (4, 1). The word word is typed with two fingers: each letter in turn is pressed by one of the fingers, which moves onto its key. Moving from (r1, c1) to (r2, c2) costs |r1 - r2| + |c1 - c2|. Each finger's starting position is free: a finger's first press costs nothing. Return the minimum total distance the fingers travel to type the word.

Example 1

word="BOAT" → 3

B is at (0, 1), O at (2, 2), A at (0, 0) and T at (3, 1). One finger types B and then A, travelling 1. The other types O and then T, travelling 2. Total 3.

Example 2

word="AZ" → 0

Each letter is typed by its own finger, placed for free, so the travel is 0.

Example 3

word="MOON" → 1

Constraints

2 ≤ len(word) ≤ 300
word consists of uppercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

String Dynamic Programming

Similar problems

Pattern With Dot and Star Hard Longest Balanced Bracket Stretch Hard Does the Text Fit the Pattern Hard Shuffle by Cutting and Swapping Hard Ways to Cross Out Hard

Input

word="BOAT"

Expected

Run checks the first 3 tests in your browser. Submit checks all 452 tests on the server, hidden ones included.