We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Distance to Type a Word Using Two Fingers

Difficulty: Hard

Problem Description

You have a keyboard layout where each English uppercase letter is located at some coordinate. Given the string word, return the minimum total distance to type such string using only two fingers. The distance between two coordinates is defined as the Manhattan distance.

Key Insights

  • Each letter corresponds to a unique coordinate on the keyboard.
  • The problem can be approached using dynamic programming to minimize the distance traveled by two fingers as they type each letter.
  • The initial positions of the fingers are free and do not contribute to the total distance.
  • The strategy involves calculating the distance for both fingers to each letter and deciding the optimal finger to use.

Space and Time Complexity

Time Complexity: O(n^2), where n is the length of the word, as we are considering all pairs of positions for the two fingers. Space Complexity: O(n), for storing the distances and the dynamic programming table.

Solution

To solve this problem, we will use a dynamic programming approach. We can maintain a DP table where dp[i][j] represents the minimum distance to type the first k letters of the word using the first finger at position i and the second finger at position j. We will iterate through the word and calculate the distance for every possible finger position, updating our DP table accordingly.

The key steps are:

  1. Identify the coordinates of each letter on the keyboard.
  2. Initialize the first entries of the DP table considering the free initial positions of the fingers.
  3. For each subsequent letter in the word, calculate the distance from the last typed letters to the current letter for both fingers.
  4. Update the DP table with the minimum distance found.

Code Solutions

def minDistance(word: str) -> int:
    # Keyboard coordinates for each letter
    keyboard = {chr(i): (i // 6, i % 6) for i in range(ord('A'), ord('Z') + 1)}
    
    n = len(word)
    # Initialize the DP table
    dp = [[float('inf')] * 26 for _ in range(26)]
    dp[-1][-1] = 0  # Initial positions of the fingers

    for k in range(n):
        cur = word[k]
        cur_x, cur_y = keyboard[cur]
        new_dp = [[float('inf')] * 26 for _ in range(26)]
        
        for i in range(26):
            for j in range(26):
                # Calculate distance if using finger 1 or finger 2
                if dp[i][j] < float('inf'):
                    # Move finger 1 to current letter
                    distance1 = abs(keyboard[chr(i + ord('A'))][0] - cur_x) + abs(keyboard[chr(i + ord('A'))][1] - cur_y)
                    new_dp[k][j] = min(new_dp[k][j], dp[i][j] + distance1)

                    # Move finger 2 to current letter
                    distance2 = abs(keyboard[chr(j + ord('A'))][0] - cur_x) + abs(keyboard[chr(j + ord('A'))][1] - cur_y)
                    new_dp[i][k] = min(new_dp[i][k], dp[i][j] + distance2)
        
        dp = new_dp
    
    return min(min(row) for row in dp)
← Back to All Questions