#1320
Minimum Distance to Type a Word Using Two Fingers
expert · 1190 · lc hard +32 · verified · 59.5% accepted · 1,047 likes · top 57%
Description
Consider a keyboard laid out in the X-Y plane where each uppercase English letter sits at a fixed coordinate — for example, 'A' is at (0, 0), 'B' at (0, 1), 'P' at (2, 3), and 'Z' at (4, 1).
Given the string word, find the minimum total Manhattan distance (|x1 - x2| + |y1 - y2|) traveled by two fingers to type every character. Both fingers may start anywhere for free and need not begin on the first letter.
Example 1:
Input: word = "CAKE"
Output: 3
Explanation: Using two fingers, one optimal way to type "CAKE" is:
Finger 1 on letter 'C' -> cost = 0
Finger 1 on letter 'A' -> cost = Distance from letter 'C' to letter 'A' = 2
Finger 2 on letter 'K' -> cost = 0
Finger 2 on letter 'E' -> cost = Distance from letter 'K' to letter 'E' = 1
Total distance = 3
Example 2:
Input: word = "HAPPY"
Output: 6
Explanation: Using two fingers, one optimal way to type "HAPPY" is:
Finger 1 on letter 'H' -> cost = 0
Finger 1 on letter 'A' -> cost = Distance from letter 'H' to letter 'A' = 2
Finger 2 on letter 'P' -> cost = 0
Finger 2 on letter 'P' -> cost = Distance from letter 'P' to letter 'P' = 0
Finger 1 on letter 'Y' -> cost = Distance from letter 'A' to letter 'Y' = 4
Total distance = 6
Code
1
2
3