Minimum Distance to Type a Word Using Two Fingers

Problem summary

We have the fixed 6-column keyboard from the statement, and we want to type word with two fingers while paying Manhattan distance for every move.

The tricky part is that the starting positions are free.

So this is not a greedy problem. A cheap move right now can block a much better split of work later.

First DP idea

The most direct state is:

dp[i][left][right] = minimum cost after typing up to index i

where left and right are the current letter positions of the two fingers.

That works, but it stores more information than we really need.

Key observation

After typing word[i], one of the two fingers must be sitting on word[i].

That means we do not need to remember both finger positions independently. We only need to know:

• the last typed character is word[i]
• where the other finger is

So we can compress the state to:

dp[other] = minimum cost when one finger is on the previous character and the other finger is at other

I also keep a special position 26 to mean:

this finger has not been used yet

That models the "free starting position" rule very naturally, because moving from that special state to any first letter costs 0.

Transition

Suppose we already typed word[i - 1], and now we want to type word[i].

Let:

• prev = word[i - 1]
• cur = word[i]

From every state dp[other], there are only two choices:

1. Use the same finger again

The finger on prev moves to cur. The other finger does not move.

So:

next[other] = min(next[other], dp[other] + dist(prev, cur))

2. Use the other finger

The other finger moves from other to cur. The finger that was on prev now becomes the resting finger.

So:

next[prev] = min(next[prev], dp[other] + dist(other, cur))

That is the whole recurrence.

Why the free start is handled correctly

Initially, after typing the first character, we can think of one finger as already being on word[0], and the other finger as still unused.

So:

dp[FREE] = 0

Later, whenever we want to use that unused finger for the first time, the move cost is still 0.

That matches the statement exactly.

import java.util.Arrays;

class Solution {
    private static final int FREE = 26;
    private static final int SIZE = 27;
    private static final int INF = 1_000_000_000;

    private int distance(int from, int to) {
        if (from == FREE || to == FREE) {
            return 0;
        }

        return Math.abs(from / 6 - to / 6) + Math.abs(from % 6 - to % 6);
    }

    public int minimumDistance(String word) {
        int[] dp = new int[SIZE];
        Arrays.fill(dp, INF);
        dp[FREE] = 0;

        for (int i = 1; i < word.length(); i++) {
            int prev = word.charAt(i - 1) - 'A';
            int cur = word.charAt(i) - 'A';
            int[] next = new int[SIZE];
            Arrays.fill(next, INF);

            for (int other = 0; other < SIZE; other++) {
                if (dp[other] == INF) {
                    continue;
                }

                next[other] = Math.min(next[other], dp[other] + distance(prev, cur));
                next[prev] = Math.min(next[prev], dp[other] + distance(other, cur));
            }

            dp = next;
        }

        int answer = INF;
        for (int value : dp) {
            answer = Math.min(answer, value);
        }
        return answer;
    }
}

Dry run on CAKE

After typing C, the active finger is on C and the other finger is still unused.

When we type A, we have two meaningful options:

• keep using the same finger: cost dist(C, A) = 2
• use the unused finger: cost 0

The second option does not help immediately, but the DP keeps both states.

Then at K, the state where the second finger is still unused becomes valuable, because we can place it on K for free.

Finally, type E with that same second finger:

• C -> A costs 2
• K -> E costs 1

Total = 3

Complexity

Time Complexity: O(27 * n), which is O(n)

At each character, we try all possible positions of the other finger.

Space Complexity: O(27), which is O(1)

Common mistakes

1. Treating the initial finger positions like real coordinates

They are free, so you should not force both fingers to start at fixed letters.

2. Keeping a full 26 x 26 state when it is not necessary

It still passes, but the transition becomes heavier than needed.

3. Forgetting that the "other finger" can still be unused

That unused state is what lets the first move of the second finger cost 0.

Pattern takeaway

This is a great example of DP state compression.

The full state starts as "where are both fingers?" But after noticing that one finger must always be on the last typed letter, the problem shrinks to just tracking the other one.