{x}
blog image

Minimum Distance to Type a Word Using Two Fingers

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 <= 300
  • word consists of uppercase English letters.

Solution Explanation: Minimum Distance to Type a Word Using Two Fingers

This problem asks for the minimum distance to type a word using two fingers on a keyboard represented as a 6x4 grid. The solution uses dynamic programming to efficiently explore the state space of finger positions.

Approach:

The core idea is to define a 3D DP array: dp[i][j][k]. This represents the minimum distance to type the first i+1 characters of the word, where:

  • i: Index of the current character being typed (0-indexed).
  • j: Position of the first finger (0-25, representing A-Z).
  • k: Position of the second finger (0-25, representing A-Z).

The base case is when i = 0. The minimum distance is 0 regardless of finger positions since we can start anywhere.

The recurrence relation considers two possibilities for each character:

  1. Place the current character (word[i]) on either finger 1 or finger 2.
  2. Calculate the distance to move the chosen finger to the new position.
  3. Find the minimum distance from the previous state (dp[i-1][prev_j][prev_k]).

Code Explanation (Python):

class Solution:
    def minimumDistance(self, word: str) -> int:
        def dist(a: int, b: int) -> int:  # Helper function to calculate Manhattan distance
            x1, y1 = divmod(a, 6)
            x2, y2 = divmod(b, 6)
            return abs(x1 - x2) + abs(y1 - y2)
 
        n = len(word)
        inf = float('inf')  # Represent infinity
        dp = [[[inf] * 26 for _ in range(26)] for _ in range(n)]
 
        # Base case: i = 0
        for j in range(26):
            dp[0][ord(word[0]) - ord('A')][j] = 0
            dp[0][j][ord(word[0]) - ord('A')] = 0
 
        # Iterate through characters
        for i in range(1, n):
            a = ord(word[i - 1]) - ord('A')
            b = ord(word[i]) - ord('A')
            d = dist(a, b)
 
            # Iterate through possible finger positions for the current character
            for j in range(26):
                dp[i][b][j] = min(dp[i][b][j], dp[i - 1][a][j] + d) #Finger 1 types
                dp[i][j][b] = min(dp[i][j][b], dp[i - 1][j][a] + d) #Finger 2 types
 
                #Special case: if the fingers were at the same spot before. We need to explore all possibilities
                if j == a:
                    for k in range(26):
                        t = dist(k, b)
                        dp[i][b][j] = min(dp[i][b][j], dp[i - 1][k][a] + t)
                        dp[i][j][b] = min(dp[i][j][b], dp[i - 1][a][k] + t)
 
        # Find the minimum distance after typing all characters
        ans = min(min(dp[n - 1][ord(word[-1]) - ord('A')]),min(dp[n-1][j][ord(word[-1]) - ord('A')] for j in range(26)))
 
        return ans

Time Complexity: O(N * 26 * 26) where N is the length of the word. The nested loops iterate through all possible states.

Space Complexity: O(N * 26 * 26) to store the DP table. This can be optimized to O(26 * 26) if we only need to store the previous row's information.

The code in other languages (Java, C++, Go) follows the same logic and algorithmic steps as the Python code, with only syntactic differences to reflect the particularities of the respective languages. The time and space complexity remain consistent across all implementations.