Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Using the nearest finger immediately can leave both fingers poorly placed for later letters. The future cost depends on the next letter index and both finger positions, so memoization can compare both choices without repeatedly solving the same remaining typing task.

Approach

Map each letter to its row and column on the six-column keyboard. Memoize the minimum remaining cost for (index, finger1, finger2). Try typing the next letter with either finger, adding its Manhattan movement distance and updating only that finger's position. An unused finger has zero first-placement cost, reflecting the free initial positions. Return zero after the final letter, and start with both fingers unused. Taking the cheaper of the two transitions at every state explores all finger assignments.

class Solution:
    def minimumDistance(self, word: str) -> int:
        @cache
        def dp(si, f1, f2):
            if si == len(word):
                return 0

            best = inf
            pos = ord(word[si]) - ord('A')
            i, j = pos // 6, pos % 6
            d1 = 0 if f1 == (-1, -1) else abs(f1[0] - i) + abs(f1[1] - j)
            best = min(best, d1 + dp(si + 1, (i, j), f2))
            d2 = 0 if f2 == (-1, -1) else abs(f2[0] - i) + abs(f2[1] - j)
            best = min(best, d2 + dp(si + 1, f1, (i, j)))
            return best

        return dp(0, (-1, -1), (-1, -1))

Complexity analysis

Let L = word.length and A = 27 possible finger positions including 'unused'. After each typed character, one finger must occupy that character, so only O(L * A) of the nominal two-finger states are reachable. With two transitions per state, time and auxiliary memo space are O(L * A) (thus O(L) for fixed A), and recursion depth is O(L).