1320. Minimum Distance to Type a Word Using Two Fingers

String
Dynamic Programming

TIME

O(n × 27)

SPACE

O(27)

Intuition

At each step, decide which finger types the current character. Use DP to track the positions of both fingers and minimize total distance.

Solution

Key Insight

One finger always just typed the previous character. So we only need to track where the "other" finger is.

State Definition

dp[i][j] = minimum cost to type first i characters where:

One finger is at word[i-1] (just typed it)
Other finger is at letter j (or j = 26 means unused/free)

Transition

For typing word[i]:

Option 1: Use the finger that typed word[i-1]

dp[i+1][j] = dp[i][j] + dist(word[i-1], word[i])

Option 2: Use the other finger (currently at position j)

dp[i+1][word[i-1]] = dp[i][j] + dist(j, word[i])  // if j != 26
dp[i+1][word[i-1]] = dp[i][j] + 0                 // if j == 26 (free)

Letter to Coordinate

def pos(c):
    idx = ord(c) - ord('A')
    return (idx // 6, idx % 6)

Distance

Manhattan distance: |x1 - x2| + |y1 - y2|

Complexity

Time: O(n × 27) = O(n)
Space: O(27) = O(1) with space optimization

Edge Cases

Same consecutive letters → 0 distance
All same letters → 0 total distance
Two distinct letters alternating → one finger each

Code

class Solution:
    def minimumDistance(self, word: str) -> int:
        """
        1320. Minimum Distance to Type a Word Using Two Fingers
        Time: O(n × 27)
        Space: O(27)
        """
        def pos(c):
            idx = ord(c) - ord('A')
            return (idx // 6, idx % 6)

        def dist(c1, c2):
            if c1 == 26:  # finger not yet placed
                return 0
            p1 = (c1 // 6, c1 % 6)
            p2 = (c2 // 6, c2 % 6)
            return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])

        # dp[j] = min cost where other finger is at letter j (26 = not placed)
        dp = [float('inf')] * 27
        dp[26] = 0  # initially, other finger is free

        prev = ord(word[0]) - ord('A')
        # First character: one finger goes there for free
        # dp stays the same, prev = first letter

        for i in range(1, len(word)):
            curr = ord(word[i]) - ord('A')
            new_dp = [float('inf')] * 27

            for j in range(27):
                if dp[j] == float('inf'):
                    continue

                # Option 1: Use finger that was at prev
                cost1 = dp[j] + dist(prev, curr)
                new_dp[j] = min(new_dp[j], cost1)

                # Option 2: Use finger that was at j (other finger)
                cost2 = dp[j] + dist(j, curr)
                new_dp[prev] = min(new_dp[prev], cost2)

            dp = new_dp
            prev = curr

        return min(dp)

import java.util.Arrays;

/**
 * 1320. Minimum Distance to Type a Word Using Two Fingers
 * Time: O(n × 27)
 * Space: O(27)
 */
class Solution {
    public int minimumDistance(String word) {
        int[] dp = new int[27];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[26] = 0;  // other finger is free initially

        int prev = word.charAt(0) - 'A';

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

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

                // Option 1: Use finger at prev
                int cost1 = dp[j] + dist(prev, curr);
                newDp[j] = Math.min(newDp[j], cost1);

                // Option 2: Use finger at j
                int cost2 = dp[j] + dist(j, curr);
                newDp[prev] = Math.min(newDp[prev], cost2);
            }

            dp = newDp;
            prev = curr;
        }

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

    private int dist(int c1, int c2) {
        if (c1 == 26) return 0;  // finger not yet placed
        int r1 = c1 / 6, col1 = c1 % 6;
        int r2 = c2 / 6, col2 = c2 % 6;
        return Math.abs(r1 - r2) + Math.abs(col1 - col2);
    }
}