Minimum Distance to Type a Word Using Two Fingers - Video Solutions
Minimum Distance to Type a Word Using Two Fingers | Detailed | Intuition | Leetcode 1320 | MIK
Minimum Distance to Type a Word Using Two Fingers - Video Solution
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 codestorywithMIK has 7,054 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
You have a keyboard layout as shown above in the X-Y plane, where each English uppercase letter is located at some coordinate.
- For example, the letter
'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 <= 300wordconsists of uppercase English letters.
Approach Overview
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.
Complexity Analysis
| 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 |