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 word word.
• 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:

1. 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 indices a and b. Manhattan distance is calculated as |x1 - x2| + |y1 - y2|, where (x1, y1) and (x2, y2) are the coordinates of the two keys.

2. 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 position ord(word[0]) - ord('A')) could be reached by either finger without any prior movement. Hence the initial cost is 0.

3. 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 or b), 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 first i characters with fingers ending at a and b.

4. 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')] and f[n - 1][j][ord(word[-1]) - ord('A')] for all j to determine the minimum value.

5. 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.

Example 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.

1. Initial State: Before starting, we assume that the two fingers can start at any two letters, with zero initial distance.

2. Typing "L": The first character we need to type is "L". We initialize our dynamic programming array f such that f[0][a][b] is 0 for all a and b because the cost of moving to the first letter is not counted.

3. 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.

4. 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.

5. 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.

6. 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] and f[3][a][ord('T') - ord('A')] for all a and b. 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

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.