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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Distance to Type a Word Using Two Fingers

Number: 1443

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Given an uppercase string word, determine the minimum total Manhattan distance required to type the word using two fingers on a special keyboard. The keyboard is laid out in the X-Y plane so that letter 'A' is at (0, 0), 'B' is at (0, 1), etc., and each movement cost is the Manhattan distance between two key coordinates. The initial positions of both fingers are free (no cost). For each letter to type (in order), you can choose which finger to move. The task is to plan finger movements such that the total moving distance is minimized.

Key Insights

  • Use dynamic programming to decide which finger to move at each letter.
  • Represent the state by the last letters that each finger pressed (or a special initial state).
  • The next letter to type is determined by the maximum of the two finger positions plus one.
  • The cost for moving a finger is the Manhattan distance between keys.
  • Leverage memoization to avoid repeated calculations in overlapping subproblems.

Space and Time Complexity

Time Complexity: O(n^2), where n is the length of the word, because each state is determined by two finger positions. Space Complexity: O(n^2) for the memoization table storing intermediate results.

Solution

We solve the problem using a recursive dynamic programming approach with memoization. Define a function f(i, j) where:

  • i: the index of the letter last typed by finger1 (or -1 if it hasn't been used yet)
  • j: the index of the letter last typed by finger2 (or -1 if it hasn't been used yet) The next letter to type has index k = max(i, j) + 1. At each step, we choose to move either finger1 or finger2 to type the next letter; if a finger has never been used (i.e. index -1), moving it incurs no cost. Otherwise, moving a finger costs the Manhattan distance between its current key and the next key. The Manhattan distance between two letters is computed by converting the letter's position to (row, col) using:   row = (letter index) // 6
      col = (letter index) % 6
    We use recursion with memoization to explore both choices at each step and return the minimal cost.

Code Solutions

# Python solution with line-by-line comments

class Solution:
    def minimumDistance(self, word: str) -> int:
        n = len(word)
        
        # Precompute coordinates for each letter on our keyboard layout.
        # Letter 'A' has index 0, so row = index // 6, col = index % 6.
        coords = [(i // 6, i % 6) for i in range(26)]
        
        # Helper function to compute Manhattan distance between two letters.
        def distance(letter1: str, letter2: str) -> int:
            x1, y1 = coords[ord(letter1) - ord('A')]
            x2, y2 = coords[ord(letter2) - ord('A')]
            return abs(x1 - x2) + abs(y1 - y2)
        
        # Use memoization to store computed states.
        memo = {}
        
        # dp function defined on state (i, j)
        # i: index of the letter last typed by finger1, j: by finger2.
        def dp(i: int, j: int) -> int:
            # Next character index to type.
            k = max(i, j) + 1
            
            # All characters have been typed.
            if k >= n:
                return 0
            # Use memoized result if already computed.
            if (i, j) in memo:
                return memo[(i, j)]
                
            # Option 1: Move finger1 to press word[k]
            cost1 = 0 if i == -1 else distance(word[i], word[k])
            option1 = cost1 + dp(k, j)
            
            # Option 2: Move finger2 to press word[k]
            cost2 = 0 if j == -1 else distance(word[j], word[k])
            option2 = cost2 + dp(i, k)
            
            # Choose the minimal cost option.
            memo[(i, j)] = min(option1, option2)
            return memo[(i, j)]
        
        # Initialize both fingers as not used (-1) and return computed cost.
        return dp(-1, -1)
        
# Example usage:
# sol = Solution()
# print(sol.minimumDistance("CAKE"))  # Expected output: 3
← Back to All Questions