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:

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

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.

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 that f[0][a][b] is 0 for all a and b 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] 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

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don't know