By Expert Funda Sunday, April 12, 2026

# 1320 Hard Dynamic Programming

Minimum Distance to Type a Word
Using Two Fingers

Given a keyboard layout and a target word, find the minimum total Manhattan distance your two fingers need to travel to type the entire word — starting from any position for free.

47.3% Acceptance
O(26N) Time Complexity
O(26) Space Complexity
Java Language
Problem Statement
Hard

You have a special keyboard with all 26 lowercase English letters laid out in a 4×6 grid (A–F on row 0, G–L on row 1, M–R on row 2, S–X on row 3, Y–Z on row 4).

You want to type a string word using two fingers. The distance to move a finger from key i to key j is the Manhattan distance: |row_i - row_j| + |col_i - col_j|. You can start both fingers anywhere for free (zero cost).

Return the minimum total distance to type the entire word.

💡
Key insight: You only ever need to track where the other finger is — one finger is always on the last typed key, so the DP state is just one integer.
The keyboard layout
Manhattan distance between any two keys = |Δrow| + |Δcol|
Example — word = "CAKE", answer = 3
Walkthrough
Finger 1
Finger 2
Current target
1
Type C → Place Finger 1 +0
Both fingers start floating. Place Finger 1 on C at (row 0, col 2) for free.
Total cost so far: 0
2
Type A → Move Finger 1 from C→A +2
C is at col 2, A is at col 0. Distance = |0−0| + |2−0| = 2.
Finger 2 stays unplaced. Total cost: 2
3
Type K → Place Finger 2 on K +0
Finger 2 was unplaced → place it directly on K at (row 1, col 4) for free. Finger 1 stays on A. Total cost: 2
4
Type E → Move Finger 2 from K→E +1
K is at (1,4), E is at (0,4). Distance = |1−0| + |4−4| = 1.
Final cost: 2 + 1 = 3 ✓
DP State Table — "CAKE"

dp[j] = minimum cost where one finger is on the current character and the other finger is at position j (26 = not yet placed).

After typing → — (free) A (0) C (2) K (10) E (4)
C 0 ∞ ∞ ∞ ∞
A 2 ∞ 0 ∞ ∞
K 7 2 5 ∞ ∞
E ✓ 8 3 6 6 ∞
→
Final answer = minimum of the last row = 3. The optimal path is the column highlighted in gold: other finger stays at A while Finger 2 handles K→E.
Java Solution — Bottom-Up DP
O(26N) O(26)
Java 
class Solution {
    public int minimumDistance(String word) {
        // dp[j] = min cost: one finger on word[i-1], other at letter j
        // j = 26 → other finger not yet placed
        int[] dp = new int[27];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[26] = 0;  // start: both fingers unplaced

        for (int i = 1; i < word.length(); i++) {
            int prev = word.charAt(i - 1) - 'A';
            int curr = word.charAt(i) - 'A';
            int[] next = new int[27];
            Arrays.fill(next, Integer.MAX_VALUE);

            for (int j = 0; j <= 26; j++) {
                if (dp[j] == Integer.MAX_VALUE) continue;

                // Choice 1: move the finger on prev → curr
                //           other finger stays at j
                next[j] = Math.min(next[j],
                    dp[j] + dist(prev, curr));

                // Choice 2: move the other finger (at j) → curr
                //           finger on prev becomes the new "other"
                next[prev] = Math.min(next[prev],
                    dp[j] + dist(j, curr));
            }
            dp = next;
        }

        int ans = Integer.MAX_VALUE;
        for (int cost : dp) ans = Math.min(ans, cost);
        return ans;
    }

    private int dist(int a, int b) {
        if (a == 26) return 0; // unplaced → free to place anywhere
        return Math.abs(a / 6 - b / 6)
             + Math.abs(a % 6 - b % 6);
    }
}
⚠️
Edge case: When j == 26 (finger not placed), dist() returns 0 — placing a finger anywhere is always free, matching the problem constraints.
All Approaches — Pros & Cons
✦ Bottom-Up DP (optimal)
O(26N) O(26)
Constant space, single pass
No recursion overhead
State encoding less obvious
Top-Down DP + Memo
O(26N) O(26N)
Intuitive recursive structure
Easy to reason about states
O(N) stack + O(26N) memo
3D DP (both positions)
O(26²N) O(26²N)
Most explicit / readable
3× redundant states
Much higher memory usage
✗ Greedy (incorrect)
O(N) O(1)
Fastest, simplest code
Fails on counter-examples
Local optimum ≠ global optimum
Continue Reading →