Minimum Distance to Type a Word Using Two Fingers

hard string dynamic programming keyboard

Problem

Each uppercase letter sits at a fixed coordinate on a keyboard laid out 6 columns wide: 'A' is at row 0, column 0, 'B' at (0, 1), 'C' at (0, 2), and so on, so letter index i lives at (i / 6, i % 6). The cost of moving a finger between two keys is the Manhattan distance |x₁ − x₂| + |y₁ − y₂|.

Type the whole word in order using two fingers and return the minimum total travel. Either finger may type any letter, the starting positions are free, and a finger that does not move incurs zero cost.

Inputword = "CAKE"

Output3

Finger 1 types C then A (cost 2); finger 2 types K then E (cost 1). Total = 3.

word (uppercase A–Z)

def minimumDistance(word):
    INF = float('inf')
    # Manhattan distance between two keys; 26 = "free / unused" finger.
    def dist(a, b):
        if a == 26 or b == 26:
            return 0
        return abs(a // 6 - b // 6) + abs(a % 6 - b % 6)

    # dp[o] = min cost so far with one finger on the previous letter
    # and the other finger resting on key o (26 means not placed yet).
    dp = [0] * 27
    prev = 26
    for ch in word:
        cur = ord(ch) - ord('A')
        ndp = [INF] * 27
        for o in range(27):
            if dp[o] == INF:
                continue
            # Move the finger that sat on prev onto cur; other stays at o.
            ndp[o] = min(ndp[o], dp[o] + dist(prev, cur))
            # Move the other finger (at o) onto cur; prev becomes resting.
            ndp[prev] = min(ndp[prev], dp[o] + dist(o, cur))
        dp = ndp
        prev = cur
    return min(dp)

function minimumDistance(word) {
  const INF = Infinity;
  // Manhattan distance between two keys; 26 = "free / unused" finger.
  const dist = (a, b) =>
    (a === 26 || b === 26) ? 0
      : Math.abs((a / 6 | 0) - (b / 6 | 0)) + Math.abs(a % 6 - b % 6);

  // dp[o] = min cost so far with one finger on the previous letter
  // and the other finger resting on key o (26 means not placed yet).
  let dp = new Array(27).fill(0);
  let prev = 26;
  for (const ch of word) {
    const cur = ch.charCodeAt(0) - 65;
    const ndp = new Array(27).fill(INF);
    for (let o = 0; o < 27; o++) {
      if (dp[o] === INF) continue;
      // Move the finger that sat on prev onto cur; other stays at o.
      ndp[o] = Math.min(ndp[o], dp[o] + dist(prev, cur));
      // Move the other finger (at o) onto cur; prev becomes resting.
      ndp[prev] = Math.min(ndp[prev], dp[o] + dist(o, cur));
    }
    dp = ndp;
    prev = cur;
  }
  return Math.min(...dp);
}

int minimumDistance(String word) {
    final int INF = Integer.MAX_VALUE;
    int[] dp = new int[27];          // dp[o] = min cost, other finger at key o
    int prev = 26;                   // 26 = "free / unused" finger
    for (char c : word.toCharArray()) {
        int cur = c - 'A';
        int[] ndp = new int[27];
        java.util.Arrays.fill(ndp, INF);
        for (int o = 0; o < 27; o++) {
            if (dp[o] == INF) continue;
            // Move the finger on prev onto cur; other stays at o.
            ndp[o] = Math.min(ndp[o], dp[o] + dist(prev, cur));
            // Move the other finger (at o) onto cur; prev rests.
            ndp[prev] = Math.min(ndp[prev], dp[o] + dist(o, cur));
        }
        dp = ndp;
        prev = cur;
    }
    int best = INF;
    for (int v : dp) best = Math.min(best, v);
    return best;
}

int dist(int a, int b) {            // Manhattan distance between two keys
    if (a == 26 || b == 26) return 0;
    return Math.abs(a / 6 - b / 6) + Math.abs(a % 6 - b % 6);
}

int dist(int a, int b) {            // Manhattan distance between two keys
    if (a == 26 || b == 26) return 0;
    return abs(a / 6 - b / 6) + abs(a % 6 - b % 6);
}

int minimumDistance(string word) {
    const int INF = 1e9;
    vector<int> dp(27, 0);          // dp[o] = min cost, other finger at key o
    int prev = 26;                  // 26 = "free / unused" finger
    for (char c : word) {
        int cur = c - 'A';
        vector<int> ndp(27, INF);
        for (int o = 0; o < 27; o++) {
            if (dp[o] == INF) continue;
            // Move the finger on prev onto cur; other stays at o.
            ndp[o] = min(ndp[o], dp[o] + dist(prev, cur));
            // Move the other finger (at o) onto cur; prev rests.
            ndp[prev] = min(ndp[prev], dp[o] + dist(o, cur));
        }
        dp = ndp;
        prev = cur;
    }
    return *min_element(dp.begin(), dp.end());
}

Explanation

At any moment one finger has just typed the most recent letter, and the other finger is resting somewhere. The crucial insight is that the only state we need to remember is where the idle finger is; the active finger is always on the previous letter, so its position is implied.

That gives a tiny DP table dp of size 27: dp[o] is the minimum total distance to have typed everything so far, with the active finger on the previous letter and the idle finger parked on key o. Index 26 is a sentinel meaning “this finger has not been placed yet,” and moving to or from it costs 0 — that is how the free starting positions are modeled.

For each new letter cur there are exactly two choices. Reuse the active finger: it travels from prev to cur, and the idle finger stays at o, so the new state keeps key o idle. Use the idle finger: it jumps from o to cur, which leaves the formerly active finger (still on prev) as the new idle one, so the new idle key is prev.

We relax both transitions into a fresh table ndp with min, then roll forward: dp = ndp and prev = cur. After the last letter the answer is the smallest value in dp, since the idle finger may end anywhere.

For "CAKE" the optimum keeps one finger on C→A (distance 2) and the other on K→E (distance 1), for a total of 3 — exactly what the DP discovers.

Time: O(n · 27) Space: O(27)