Problem Statement in English

You’re given a string word that you want to type using two fingers. The letters are layed out in a 6 x 5 grid with the letter A at the top left, and the letter Z at the cell index (4, 1) (0-indexed).

The cost of moving a finger from cell x to cell y is the Manhattan distance, or |x[0] - y[0]| + |x[1] - y[1]|.

If a finger is on a letter and you want to use that finger to type that letter, the cost of moving the finger is 0 (i.e., it’s already there).

You can choose any starting position for each finger. Return the minimum total distance to type all the characters in word.

Approach

You genuinely don’t need to overthink this.

Fundamentally, for each letter you can choose to type it with either finger. So you need to calculate both possibilities and take the minimum. Time to DP.

We need a way to convert the letter to its position on the grid. We can do that by using the ASCII value of the letter and doing some math.

The x and y coordinates of an ASCII letter can be calculated as follows:

  • x = (ASCII value of the letter - ASCII value of ‘A’) // 6
  • y = (ASCII value of the letter - ASCII value of ‘A’) % 6

Now we can calculate the distance between two letters using the Manhattan distance formula.

Next up, we need to implement the DP. We can use a recursive function with memoization to calculate the minimum distance. The function will take the current index of the letter we want to type, and the positions of both fingers, and return the minimum distance to type the remaining letters.

And we’re done!

Solution in Python


class Solution:
    def minimumDistance(self, word: str) -> int:

        def dist(a, b):
            if a == 26 or b == 26:
                return 0
            return abs(a // 6 - b // 6) + abs(a % 6 - b % 6)

        @cache
        def solve(i, f1, f2):
            if i == len(word):
                return 0

            cur = ord(word[i]) - ord("A")

            move1 = dist(f1, cur) + solve(i + 1, cur, f2)
            move2 = dist(f2, cur) + solve(i + 1, f1, cur)

            return min(move1, move2)

        return solve(0, 26, 26)

Complexity

  • Time: $O(N * 26 ^ 2)$
    Since we have N letters in the word, and for each letter we have 26 possible positions for each finger.

  • Space: $O(N * 26 ^ 2)$
    Since we are using memoization to store the results of the recursive function.

Mistakes I Made

I overcomplicated the problem and had to look up the solution.

And we are done.