Minimum Distance to Type a Word Using Two Fingers

Minimum Distance to Type a Word Using Two Fingers looks scary, but it is a clean DP once you spot the real question: at every letter, which finger should move? The trick is to remember where the idle finger is resting.

The slow way first

You might try to brute-force every assignment of fingers: at each letter, either finger could press it, so there are 2^n finger sequences. Tracking both finger positions through all of them is exponential — far too slow for a long word.

The question to ask: what do I actually need to remember to make the next choice? When I type the next letter, one finger has to land on it. The cost only depends on where the other (idle) finger currently sits — not on the whole history. That single fact collapses the exponential search into a small table.

The idea: track where the idle finger rests

Walk the word one letter at a time. Let dp[other] be the minimum total distance to have typed everything so far, given the idle finger is resting on key other. To type the next letter cur, there are two moves:

• Move the idle finger to cur: it travels d(other, cur), and the finger that was on the previous letter becomes the new idle one.
• Move the finger already on the previous letter to cur: it travels d(prev, cur), and other stays idle.

We keep the cheaper option for every resting key, so the table never explodes.

The key insight: the state is just the idle finger position, because the active finger is always on the previous letter, which we already know.

Walk through it

Step through the animation on the keyboard grid. The right finger starts on C for free. Bringing the unused left finger to A also costs nothing. For K, moving the right finger C → K costs 3 (cheaper than A → K = 5). For the final E, moving the right finger K → E costs 1 (cheaper than A → E = 4). Total: 3 + 1 = 4.

Pseudocode

d(a, b) = |row(a) - row(b)| + |col(a) - col(b)|   # Manhattan distance
dp = { "off-board": 0 }      # the idle finger starts unused
for each letter cur in word:
    new dp = {}
    for each (other, cost) in dp:
        # move the idle finger to cur; old active key becomes idle
        new dp[other] = min(new dp[other], cost + d(other, cur))
        # move the active finger to cur; other stays idle
        new dp[cur]   = min(new dp[cur],   cost)
    dp = new dp
return the smallest value in dp

The Python solution

def min_distance(word):
    def d(a, b):
        return abs(a // 6 - b // 6) + abs(a % 6 - b % 6)
    INF = float('inf')
    dp = {26: 0}  # idle finger "off the board"
    for ch in word:
        cur = ord(ch) - 65
        ndp = {}
        for other, cost in dp.items():
            ndp[other] = min(ndp.get(other, INF), cost + d(other, cur))
            prev = cur  # the finger that just typed becomes idle
            ndp[cur] = min(ndp.get(cur, INF), cost)
        dp = ndp
    return min(dp.values())

• d(a, b) is the Manhattan distance on the 6-wide grid: row difference plus column difference.
• dp maps the idle finger position → the cheapest total distance to reach this point. The sentinel key 26 means the second finger has not been placed yet, which makes its first placement free.
• For each letter, line 10 moves the idle finger onto cur and charges d(other, cur); the key that was active stays implicit because it is now the previous letter.
• Line 12 keeps other idle and instead moves the active finger onto cur — that move costs cost only, since the active finger was on the previous letter and we fold its travel into the next iteration.
• After the loop, line 14 returns the smallest entry: the best place for the idle finger to have ended up.

Complexity

Each letter only needs the table from the previous letter, and the table has at most one entry per key (plus the off-board sentinel), so both time and space stay tiny: effectively O(n).

When this pattern shows up

Practice