Watch 10 video solutions for Minimum Distance to Type a Word Using Two Fingers, a hard level problem involving String, Dynamic Programming. This walkthrough by Algorithms Casts has 2,835 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You have a keyboard layout as shown above in the X-Y plane, where each English uppercase letter is located at some coordinate.
'A' is located at coordinate (0, 0), the letter 'B' is located at coordinate (0, 1), the letter 'P' is located at coordinate (2, 3) and the letter 'Z' is located at coordinate (4, 1).Given the string word, return the minimum total distance to type such string using only two fingers.
The distance between coordinates (x1, y1) and (x2, y2) is |x1 - x2| + |y1 - y2|.
Note that the initial positions of your two fingers are considered free so do not count towards your total distance, also your two fingers do not have to start at the first letter or the first two letters.
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
Constraints:
2 <= word.length <= 300word consists of uppercase English letters.Problem Overview: You type a word using two fingers on a virtual keyboard containing the letters A–Z. Each move costs the Manhattan distance between keys. The goal is to minimize the total movement required to type the entire word.
Approach 1: Dynamic Programming with State Representation (O(n * 26 * 26) time, O(26 * 26) space)
Model the typing process with dynamic programming where the state represents the positions of both fingers. Use dp[i][f1][f2] or a compressed map where f1 and f2 store the characters currently under each finger while typing index i of the word. For every new character, choose which finger presses it and add the Manhattan distance between the previous key and the new key. The keyboard coordinates are computed from the character index (A=0 … Z=25) mapped onto a 6‑column grid. This brute-force DP checks all possible finger placements, ensuring the minimum cost is captured for each step.
Approach 2: Dynamic Programming with Two-dimensional Array (O(n * 26) time, O(26) space)
Observation: only one finger needs an explicit state. The other finger implicitly sits on the previously typed character. Maintain dp[x] where x represents the letter currently under the "free" finger while the other finger typed the last character. When processing the next letter, either move the active finger or switch to the free finger and update its position. This reduces the state space dramatically from 26×26 possibilities to just 26. Each transition computes the Manhattan distance between letters and updates the minimum movement cost.
Both approaches rely on precomputing keyboard coordinates and calculating distance using |r1-r2| + |c1-c2|. This problem is a classic application of dynamic programming combined with efficient state transitions over a string. The key insight is recognizing that the second finger can remain "free" until it becomes beneficial to move it.
Recommended for interviews: The optimized DP with a one‑finger state (O(n * 26)) is what most interviewers expect. The full state DP demonstrates correct reasoning about finger positions, but the reduced-state version shows stronger problem‑solving skills and the ability to simplify DP transitions.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with State Representation | O(n * 26 * 26) | O(26 * 26) | Good for understanding the full DP state of both finger positions |
| Optimized DP with Two-dimensional Array | O(n * 26) | O(26) | Preferred solution for interviews and large inputs |