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.
This approach involves using a dynamic programming technique to keep track of the minimum cost for typing the word with two fingers. We define a function that returns the minimum cost to type from a given position with a specific state defined by finger positions.
The position of each character on the keyboard can be represented in terms of X and Y coordinates. Movements from character to character can thus be calculated using Manhattan distance.
We use a memoization technique to save previously computed states to avoid redundant calculations, ensuring efficiency.
This code uses a recursive function `dp_solve` which takes the current index `i` and the positions of the two fingers `f1`, `f2` and returns the minimum cost to type the word from that point onwards. The base case is when `i` equals the length of the word, returning 0 as there's nothing left to type.
The function `dist` calculates the Manhattan distance between two positions. The memoization technique uses a dictionary `dp` to store already computed results for specific states (i, f1, f2), thus reducing redundant computations.
Python
JavaScript
Time Complexity: O(n*26*26), where n is the length of the word and 26 represents possible states for each finger (since there are 26 letters).
Space Complexity: O(n*26*26) for storing results in the dp dictionary.
This approach is a variation of the dynamic programming solution, using a two-dimensional array to maintain a tabulation of results instead of recursion with memoization. We precompute distances and use a bottom-up DP approach to fill our dp table.
At each step, we decide the best possible move for each finger to type the character at the current index with minimum cost.
This C++ solution employs a bottom-up dynamic programming approach, using a matrix to track the minimum cost of reaching each letter with each finger. We iteratively build the solution by updating this matrix based on potential movements from one letter to the next.
Time Complexity: O(n * 26^2) where n is the length of the word.
Space Complexity: O(n * 26) for storing DP states.
We define f[i][j][k] to represent the minimum distance after typing word[i], with finger 1 at position j and finger 2 at position k. Here, positions j and k represent the numbers corresponding to the letters, ranging from [0,..25]. Initially, f[i][j][k] = infty.
We implement a function dist(a, b) to represent the distance between positions a and b, i.e., dist(a, b) = |\frac{a}{6} - \frac{b}{6}| + |a bmod 6 - b bmod 6|.
Next, we consider typing word[0], i.e., the case with only one letter. There are two choices:
word[0], and finger 2 is at any position. In this case, f[0][word[0]][k] = 0, where k \in [0,..25].word[0], and finger 1 is at any position. In this case, f[0][k][word[0]] = 0, where k \in [0,..25].Then we consider typing word[1,..n-1]. Let the positions of the previous letter and the current letter be a and b, respectively. Next, we discuss the following cases:
If the current finger 1 is at position b, we enumerate the position j of finger 2. If the previous position a was also the position of finger 1, then f[i][b][j] = min(f[i][b][j], f[i-1][a][j] + dist(a, b)). If the position of finger 2 is the same as the previous position a, i.e., j = a, then we enumerate the position k of finger 1 in the previous position. In this case, f[i][b][j] = min(f[i][b][j], f[i-1][k][a] + dist(k, b)).
Similarly, if the current finger 2 is at position b, we enumerate the position j of finger 1. If the previous position a was also the position of finger 2, then f[i][j][b] = min(f[i][j][b], f[i-1][j][a] + dist(a, b)). If the position of finger 1 is the same as the previous position a, i.e., j = a, then we enumerate the position k of finger 2 in the previous position. In this case, f[i][j][b] = min(f[i][j][b], f[i-1][a][k] + dist(k, b)).
Finally, we enumerate the positions of finger 1 and finger 2 at the last position and take the minimum value as the answer.
The time complexity is O(n times |\Sigma|^2), and the space complexity is O(n times |\Sigma|^2). Here, n is the length of the string word, and |\Sigma| is the size of the alphabet, which is 26 in this problem.
| Approach | Complexity |
|---|---|
| Dynamic Programming with State Representation | Time Complexity: O(n*26*26), where n is the length of the word and 26 represents possible states for each finger (since there are 26 letters). Space Complexity: O(n*26*26) for storing results in the dp dictionary. |
| Dynamic Programming with Two-dimensional Array | Time Complexity: O(n * 26^2) where n is the length of the word. Space Complexity: O(n * 26) for storing DP states. |
| Dynamic Programming | — |
| 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 |
Leetcode 1320: Minimum Distance to Type a Word Using Two Fingers • Algorithms Casts • 2,835 views views
Watch 9 more video solutions →Practice Minimum Distance to Type a Word Using Two Fingers with our built-in code editor and test cases.
Practice on FleetCode