1320. Minimum Distance to Type a Word Using Two Fingers
Problem Description
In this problem, we are presented with a virtual QWERTY keyboard placed on a Cartesian plane where each letter corresponds to specific coordinates. The layout is 5 rows by 6 columns, and we want to type a given word using two fingers. The challenge is to minimize the total distance traveled by the two fingers when typing the word. The distance between any two keys is the sum of the absolute differences in their respective x (row) and y (column) coordinates.
Given a string word
, our job is to compute the minimum total distance required to type the entire word using only two fingers. It's important to note that the initial positions of the fingers are not fixed and don't contribute to the distance; this means that you can start with your fingers positioned on any two letters, whichever results in the least amount of total movement.
Intuition
The key to solving this problem is to realize that it is a dynamic programming problem. The underlying idea is that the minimum distance to type a word using two fingers can be broken down into smaller sub-problems, each contributing to the final overall distance.
At each step, when we move to type a new letter, we face a choice: which finger to move. This choice depends on the positions of both fingers and the current letter that needs to be typed. Our aim is to make a decision that leads to the least total distance moved by the time the entire word is typed.
To implement this, we use a three-dimensional array f
to store the state of our solution. The indexes are as follows:
- The first index
i
corresponds to the position in the wordword
. - The second index
a
corresponds to the position of one finger on the keyboard (the position of the finger that was previously used to type the last character). - The third index
b
corresponds to the position of the other finger on the keyboard (the position of the finger that was not used to type the last character).
The value at f[i][a][b]
represents the minimum distance to type the word up to the i-th
character, with one finger on the a-th
key and the other on the b-th
key.
The dist
function helps calculate the Manhattan distance between any two keys on the keyboard, which is necessary to determine how much distance is traveled when a finger moves from one letter to another.
We iterate through each letter of the word, updating our dynamic programming array with the minimum distances found. The updates consider the possible scenarios, whether we move the last-used finger or the idle finger to reach the new letter.
Finally, we look for the smallest value in the last layer of our f
array, which will give us the minimum total distance needed to type the entire word.
Learn more about Dynamic Programming patterns.
Solution Approach
The solution uses dynamic programming as an algorithmic paradigm. We leverage a three-dimensional table f[i][a][b]
to track the optimal solution up to the i-th
character of the word, where finger 1 last typed at keyboard position a
and finger 2 last typed at keyboard position b
.
Here's a step-by-step approach of the algorithm:
-
Dist Function:
- We first define a helper function
dist(a, b)
that calculates the Manhattan distance between any two keys on the keyboard represented by their flattened indicesa
andb
. Manhattan distance is calculated as|x1 - x2| + |y1 - y2|
, where(x1, y1)
and(x2, y2)
are the coordinates of the two keys.
- We first define a helper function
-
Initialization:
- Initialize the dynamic programming array
f
with infinity (inf
) for all possible states since initially we have no steps taken, and we want to find minimum values as we progress. - We also initialize the first set of movements in
f
at index 0, indicating that the first letter (at positionord(word[0]) - ord('A')
) could be reached by either finger without any prior movement. Hence the initial cost is 0.
- Initialize the dynamic programming array
-
Populating the DP Table:
- We iterate over each character of the word starting from the second character, updating
f[i][a][b]
with the minimum possible distances:- If we use the same finger as the last move (either
a
orb
), we calculate the distance from the last character to the current character and add it to the previous state's cost. - If the newly-typed character is the same as the previous character, we consider pivoting the idle finger (
j
) around the keyboard to see if that leads to a reduction in total distance for subsequent moves. - Each update ensures that
f[i][a][b]
is the minimal distance required to type the firsti
characters with fingers ending ata
andb
.
- If we use the same finger as the last move (either
- We iterate over each character of the word starting from the second character, updating
-
Extracting the Answer:
- Once we've gone through the entire word, the answer to the problem is the minimum total distance found in the last layer of the dynamic programming table.
- We consider two scenarios for the last movement - either we moved finger 1 or finger 2 to type the last character. So we look at
f[n - 1][ord(word[-1]) - ord('A')]
andf[n - 1][j][ord(word[-1]) - ord('A')]
for allj
to determine the minimum value.
-
Return the Result:
- We return the minimum of these two values as the final answer.
In summary, the solution leverages dynamic programming to systematically calculate the cumulative distances for every step of typing the word. It considers both possible movements at each step (moving either finger) and keeps updating the table with the minimum distances found thus far - effectively exploring and memorizing the cost of all viable typing paths to find the most efficient one.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's use the word "LEET" as a simple example to illustrate the solution approach. We'll walk through the dynamic programming process to find the minimum total distance two fingers must travel to type "LEET" on our virtual QWERTY keyboard.
-
Initial State: Before starting, we assume that the two fingers can start at any two letters, with zero initial distance.
-
Typing "L": The first character we need to type is "L". We initialize our dynamic programming array
f
such thatf[0][a][b]
is 0 for alla
andb
because the cost of moving to the first letter is not counted. -
Typing "E": Now we need to type the second character, "E". Our fingers are at the start, so we have two scenarios:
- Move finger 1 from "L" to "E" and keep finger 2 where it was.
- Move finger 2 from its starting position to "E" and keep finger 1 on "L".
We calculate the Manhattan distances for both scenarios using the
dist
function and update our dynamic programming array with the lowest values. -
Typing "E" again: The next character is the same, "E". We have two fingers positioned, one on "L" and the other potentially on "E". For this character, we have to decide which finger to move if at all. Since it's the same letter, there might not be a need to move either finger, but we still check all scenarios:
- Keep the finger on "E" stationary (since it's the same letter), move the other finger around to other keys, if it'll help reduce the distance for the next character.
- Move the finger from "L" to "E" if it was not already moved.
We update the array
f
for the least distances. -
Typing "T": Lastly, we need to type "T", and the fingers are at "E" and potentially some other letter. We once again calculate the distance for each scenario:
- Moving finger 1 from "E" to "T".
- Moving finger 2 from its current position to "T".
We choose the move with the smallest distance and update the dynamic programming array with the new values.
-
Conclusion: After considering the entire word, the minimum distance will be the smallest number found in our DP array for the final character. We have two cases for the last character:
- The ending position of finger 1 is the index of "T", and we consider all possible positions of finger 2.
- The ending position of finger 2 is the index of "T", and we consider all possible positions of finger 1.
We look at
f[3][ord('T') - ord('A')][b]
andf[3][a][ord('T') - ord('A')]
for alla
andb
. The minimum of all these is the answer to our problem: the minimum total distance required to type "LEET".
By thoroughly examining each possible move, considering the current and the past position of each finger, and continuously selecting the minimum distance at each step, the dynamic programming approach allows us to efficiently solve this problem.
Solution Implementation
1from math import inf
2
3class Solution:
4 def minimumDistance(self, word: str) -> int:
5 # Helper function to calculate the distance between two keys on the keyboard
6 def calculate_distance(key1: int, key2: int) -> int:
7 row1, col1 = divmod(key1, 6)
8 row2, col2 = divmod(key2, 6)
9 return abs(row1 - row2) + abs(col1 - col2)
10
11 # Length of the word
12 word_length = len(word)
13
14 # Initialize the 3D array for DP with positive infinity
15 dp = [[[inf] * 26 for _ in range(26)] for _ in range(word_length)]
16
17 # Set the initial positions of the fingers to the first letter with zero distance
18 for j in range(26):
19 dp[0][ord(word[0]) - ord('A')][j] = 0
20 dp[0][j][ord(word[0]) - ord('A')] = 0
21
22 # Fill in the dp array for each letter in the word
23 for i in range(1, word_length):
24 prev_key = ord(word[i - 1]) - ord('A')
25 current_key = ord(word[i]) - ord('A')
26 travel_distance = calculate_distance(prev_key, current_key)
27 for j in range(26):
28 # Update the state where the current finger is on the current letter and the other is on one of the 26 letters
29 dp[i][current_key][j] = min(dp[i][current_key][j], dp[i - 1][prev_key][j] + travel_distance)
30 dp[i][j][current_key] = min(dp[i][j][current_key], dp[i - 1][j][prev_key] + travel_distance)
31 # If the other finger is on the previous letter, then update the distances accordingly for all keys
32 if j == prev_key:
33 for k in range(26):
34 switching_distance = calculate_distance(k, current_key)
35 dp[i][current_key][j] = min(dp[i][current_key][j], dp[i - 1][k][prev_key] + switching_distance)
36 dp[i][j][current_key] = min(dp[i][j][current_key], dp[i - 1][prev_key][k] + switching_distance)
37
38 # Find the minimum distance for the last letter
39 final_key_positions = dp[word_length - 1][ord(word[-1]) - ord('A')]
40 min_distance_with_final_key = min(final_key_positions)
41 min_distance_with_final_key_other = min(dp[word_length - 1][j][ord(word[-1]) - ord('A')] for j in range(26))
42
43 # Return the minimum of both distances as the result
44 return int(min(min_distance_with_final_key, min_distance_with_final_key_other))
45
1import java.util.Arrays;
2
3class Solution {
4 // This function calculates the minimum total distance to type a word using two fingers
5 public int minimumDistance(String word) {
6 int n = word.length();
7 final int INF = Integer.MAX_VALUE / 2; // Effective infinity to represent an unattainable large number
8 int[][][] dp = new int[n][26][26]; // 3D DP array to store minimum distances
9
10 // Initialize all distances in dp array to infinity
11 for (int[][] layer : dp) {
12 for (int[] row : layer) {
13 Arrays.fill(row, INF);
14 }
15 }
16
17 // Base case initialization: Position both fingers over the first character with zero distance traveled
18 for (int j = 0; j < 26; ++j) {
19 dp[0][word.charAt(0) - 'A'][j] = 0;
20 dp[0][j][word.charAt(0) - 'A'] = 0;
21 }
22
23 // Building the dp solution
24 for (int i = 1; i < n; ++i) {
25 int previousCharIndex = word.charAt(i - 1) - 'A';
26 int currentCharIndex = word.charAt(i) - 'A';
27 int d = distanceBetweenKeys(previousCharIndex, currentCharIndex);
28
29 for (int j = 0; j < 26; ++j) {
30 dp[i][currentCharIndex][j] = Math.min(dp[i][currentCharIndex][j], dp[i - 1][previousCharIndex][j] + d);
31 dp[i][j][currentCharIndex] = Math.min(dp[i][j][currentCharIndex], dp[i - 1][j][previousCharIndex] + d);
32
33 // If one finger remains on the previous character, compute distance for every possible position of the other finger
34 if (j == previousCharIndex) {
35 for (int k = 0; k < 26; ++k) {
36 int t = distanceBetweenKeys(k, currentCharIndex);
37 dp[i][currentCharIndex][j] = Math.min(dp[i][currentCharIndex][j], dp[i - 1][k][previousCharIndex] + t);
38 dp[i][j][currentCharIndex] = Math.min(dp[i][j][currentCharIndex], dp[i - 1][previousCharIndex][k] + t);
39 }
40 }
41 }
42 }
43
44 // Find the minimum distance after typing all characters
45 int ans = INF;
46 for (int j = 0; j < 26; ++j) {
47 ans = Math.min(ans, dp[n - 1][j][word.charAt(n - 1) - 'A']);
48 ans = Math.min(ans, dp[n - 1][word.charAt(n - 1) - 'A'][j]);
49 }
50
51 return ans;
52 }
53
54 // Helper function to calculate the Manhattan distance between two keys indexed by a and b
55 private int distanceBetweenKeys(int a, int b) {
56 int x1 = a / 6, y1 = a % 6; // Convert index to 2D keyboard coordinates assuming 6 keys in a row
57 int x2 = b / 6, y2 = b % 6;
58 // Return Manhattan distance between the two points
59 return Math.abs(x1 - x2) + Math.abs(y1 - y2);
60 }
61}
62
1class Solution {
2public:
3 // Method to calculate the minimum distance to type a word using two fingers
4 int minimumDistance(string word) {
5 int n = word.size(); // Get the size of the word
6 const int INF = 1 << 30; // Define infinity as a very large number
7
8 // 3D vector to store the minimum distance states
9 // f[i][j][k] will represent the minimum distance after typing i-th character
10 // with one finger on j-th character and the other on k-th character
11 vector<vector<vector<int>>> dp(n, vector<vector<int>>(26, vector<int>(26, INF)));
12
13 // Initial state: The cost of having each finger on the first character is 0
14 for (int j = 0; j < 26; ++j) {
15 dp[0][word[0] - 'A'][j] = 0;
16 dp[0][j][word[0] - 'A'] = 0;
17 }
18
19 // Calculate the minimum distance for each character in the word
20 for (int i = 1; i < n; ++i) {
21 int prev_char = word[i - 1] - 'A';
22 int cur_char = word[i] - 'A';
23 int d = dist(prev_char, cur_char);
24
25 for (int j = 0; j < 26; ++j) {
26 dp[i][cur_char][j] = min(dp[i][cur_char][j], dp[i - 1][prev_char][j] + d);
27 dp[i][j][cur_char] = min(dp[i][j][cur_char], dp[i - 1][j][prev_char] + d);
28
29 // Only update if the previous character is the same as one of the fingers' positions
30 if (j == prev_char) {
31 for (int k = 0; k < 26; ++k) {
32 int t = dist(k, cur_char);
33 dp[i][cur_char][j] = min(dp[i][cur_char][j], dp[i - 1][k][prev_char] + t);
34 dp[i][j][cur_char] = min(dp[i][j][cur_char], dp[i - 1][prev_char][k] + t);
35 }
36 }
37 }
38 }
39
40 // Find the minimum distance after typing the entire word
41 int ans = INF;
42 for (int j = 0; j < 26; ++j) {
43 ans = min(ans, dp[n - 1][word[n - 1] - 'A'][j]);
44 ans = min(ans, dp[n - 1][j][word[n - 1] - 'A']);
45 }
46
47 // Return the minimum distance
48 return ans;
49 }
50
51 // Helper method to calculate the distance between two characters
52 int dist(int a, int b) {
53 int x1 = a / 6, y1 = a % 6; // Get the grid position of character a
54 int x2 = b / 6, y2 = b % 6; // Get the grid position of character b
55 return abs(x1 - x2) + abs(y1 - y2); // Return the Manhattan distance between the two positions
56 }
57};
58
1// Method to calculate the minimum distance to type a word using two fingers
2function minimumDistance(word: string): number {
3 const n: number = word.length; // Get the length of the word
4 const INF: number = 1 << 30; // Define infinity as a very large number
5
6 // 3D array to store the minimum distance states
7 // dp[i][j][k] will represent the minimum distance after typing i-th
8 // character with one finger on j-th character and the other on k-th character
9 let dp: number[][][] = Array.from({ length: n }, () =>
10 Array.from({ length: 26 }, () => Array(26).fill(INF))
11 );
12
13 // Initial state: The cost of having each finger on the first character is 0
14 for (let j = 0; j < 26; j++) {
15 dp[0][word.charCodeAt(0) - 'A'.charCodeAt(0)][j] = 0;
16 dp[0][j][word.charCodeAt(0) - 'A'.charCodeAt(0)] = 0;
17 }
18
19 // Calculate the minimum distance for each character in the word
20 for (let i = 1; i < n; i++) {
21 const prevChar: number = word.charCodeAt(i - 1) - 'A'.charCodeAt(0);
22 const curChar: number = word.charCodeAt(i) - 'A'.charCodeAt(0);
23 const distance: number = calcDistance(prevChar, curChar);
24
25 for (let j = 0; j < 26; j++) {
26 dp[i][curChar][j] = Math.min(dp[i][curChar][j], dp[i - 1][prevChar][j] + distance);
27 dp[i][j][curChar] = Math.min(dp[i][j][curChar], dp[i - 1][j][prevChar] + distance);
28
29 // Only update if the previous character is the same as one of the fingers' positions
30 if (j === prevChar) {
31 for (let k = 0; k < 26; k++) {
32 const temp: number = calcDistance(k, curChar);
33 dp[i][curChar][j] = Math.min(dp[i][curChar][j], dp[i - 1][k][prevChar] + temp);
34 dp[i][j][curChar] = Math.min(dp[i][j][curChar], dp[i - 1][prevChar][k] + temp);
35 }
36 }
37 }
38 }
39
40 // Find the minimum distance after typing the entire word
41 let answer: number = INF;
42 for (let j = 0; j < 26; j++) {
43 answer = Math.min(answer, dp[n - 1][word.charCodeAt(n - 1) - 'A'.charCodeAt(0)][j]);
44 answer = Math.min(answer, dp[n - 1][j][word.charCodeAt(n - 1) - 'A'.charCodeAt(0)]);
45 }
46
47 // Return the minimum distance
48 return answer;
49}
50
51// Helper method to calculate the Manhattan distance between two characters
52function calcDistance(a: number, b: number): number {
53 const x1: number = Math.floor(a / 6), y1: number = a % 6; // Get the grid position of character a
54 const x2: number = Math.floor(b / 6), y2: number = b % 6; // Get the grid position of character b
55 return Math.abs(x1 - x2) + Math.abs(y1 - y2); // Return the Manhattan distance between the two positions
56}
57
Time and Space Complexity
Time Complexity
The given code uses three nested loops: the outermost loop runs over the length of the string word
, and the two innermost loops both iterate 26 times, which corresponds to the number of letters in the alphabet.
The time complexity is thus O(N * 26 * 26)
, where N
is the length of the string word
, because for each character in word
(N iterations), the algorithm updates the f
matrix for every possible pair of keys (26 * 26 iterations).
Space Complexity
The space complexity of the code is dominated by the size of the 3-dimensional array f
, which has dimensions [N][26][26]
.
Hence, the space complexity is O(N * 26 * 26)
, as the code allocates memory for N * 26 * 26
integers, where N
is the length of the string word
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which two pointer techniques do you use to check if a string is a palindrome?
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first