Code Implementation

from functools import lru_cache

def minDistance(word: str) -> int:
    def pos(c):
        idx = ord(c) - ord('A')
        return (idx // 6, idx % 6)
    
    n = len(word)
    
    @lru_cache(None)
    def dp(i, f1, f2):
        if i == n:
            return 0
        p = pos(word[i])
        res = float('inf')
        # Move finger1
        if f1 == -1:
            cost1 = 0
        else:
            f1p = pos(word[f1])
            cost1 = abs(f1p[0] - p[0]) + abs(f1p[1] - p[1])
        res = min(res, cost1 + dp(i+1, i, f2))
        # Move finger2
        if f2 == -1:
            cost2 = 0
        else:
            f2p = pos(word[f2])
            cost2 = abs(f2p[0] - p[0]) + abs(f2p[1] - p[1])
        res = min(res, cost2 + dp(i+1, f1, i))
        return res

    return dp(0, -1, -1)
      

#include <vector>
#include <string>
#include <algorithm>
using namespace std;

class Solution {
public:
    int minDistance(string word) {
        int n = word.size();
        vector<vector<vector<int>>> dp(n+1, vector<vector<int>>(n+1, vector<int>(n+1, -1)));
        
        auto pos = [](char c) {
            int idx = c - 'A';
            return make_pair(idx / 6, idx % 6);
        };
        
        function<int(int,int,int)> dfs = [&](int i, int f1, int f2) {
            if (i == n) return 0;
            if (dp[i][f1+1][f2+1] != -1) return dp[i][f1+1][f2+1];
            auto [x, y] = pos(word[i]);
            int res = INT_MAX;
            // Move finger1
            int cost1 = 0;
            if (f1 != -1) {
                auto [fx, fy] = pos(word[f1]);
                cost1 = abs(fx - x) + abs(fy - y);
            }
            res = min(res, cost1 + dfs(i+1, i, f2));
            // Move finger2
            int cost2 = 0;
            if (f2 != -1) {
                auto [fx, fy] = pos(word[f2]);
                cost2 = abs(fx - x) + abs(fy - y);
            }
            res = min(res, cost2 + dfs(i+1, f1, i));
            return dp[i][f1+1][f2+1] = res;
        };
        return dfs(0, -1, -1);
    }
};
      

import java.util.*;

class Solution {
    public int minDistance(String word) {
        int n = word.length();
        Integer[][][] memo = new Integer[n+1][n+1][n+1];
        
        int[] pos(char c) {
            int idx = c - 'A';
            return new int[]{idx / 6, idx % 6};
        }

        return dfs(0, -1, -1, word, memo);
    }
    
    private int dfs(int i, int f1, int f2, String word, Integer[][][] memo) {
        int n = word.length();
        if (i == n) return 0;
        if (memo[i][f1+1][f2+1] != null) return memo[i][f1+1][f2+1];
        int[] p = pos(word.charAt(i));
        int res = Integer.MAX_VALUE;
        // Move finger1
        int cost1 = 0;
        if (f1 != -1) {
            int[] f1p = pos(word.charAt(f1));
            cost1 = Math.abs(f1p[0] - p[0]) + Math.abs(f1p[1] - p[1]);
        }
        res = Math.min(res, cost1 + dfs(i+1, i, f2, word, memo));
        // Move finger2
        int cost2 = 0;
        if (f2 != -1) {
            int[] f2p = pos(word.charAt(f2));
            cost2 = Math.abs(f2p[0] - p[0]) + Math.abs(f2p[1] - p[1]);
        }
        res = Math.min(res, cost2 + dfs(i+1, f1, i, word, memo));
        memo[i][f1+1][f2+1] = res;
        return res;
    }
    
    private int[] pos(char c) {
        int idx = c - 'A';
        return new int[]{idx / 6, idx % 6};
    }
}
      

var minDistance = function(word) {
    const n = word.length;
    const memo = new Map();
    function pos(c) {
        const idx = c.charCodeAt(0) - 65;
        return [Math.floor(idx / 6), idx % 6];
    }
    function dp(i, f1, f2) {
        const key = i + ',' + f1 + ',' + f2;
        if (memo.has(key)) return memo.get(key);
        if (i === n) return 0;
        const [x, y] = pos(word[i]);
        let res = Infinity;
        // Move finger1
        let cost1 = 0;
        if (f1 !== -1) {
            const [fx, fy] = pos(word[f1]);
            cost1 = Math.abs(fx - x) + Math.abs(fy - y);
        }
        res = Math.min(res, cost1 + dp(i+1, i, f2));
        // Move finger2
        let cost2 = 0;
        if (f2 !== -1) {
            const [fx, fy] = pos(word[f2]);
            cost2 = Math.abs(fx - x) + Math.abs(fy - y);
        }
        res = Math.min(res, cost2 + dp(i+1, f1, i));
        memo.set(key, res);
        return res;
    }
    return dp(0, -1, -1);
};
      

Problem Description

You are given a string word consisting of uppercase English letters. You have a virtual keyboard with the layout of the English alphabet in a 6-column by 5-row grid (like a phone keypad, from 'A' to 'Z', left to right, top to bottom).

You have two fingers, and both start off-screen (not on any key). You want to type the entire word in order, one letter at a time, using either finger for each letter. The cost to move a finger from one key to another is the Manhattan distance (the sum of the horizontal and vertical moves between keys). Moving a finger from off-screen to any key costs 0.

Your goal is to find the minimum total distance required to type the whole word using the two fingers, optimally switching between them as needed.

• Each letter must be typed in order.
• Both fingers can be used in any order for each letter.
• Each finger can be moved any number of times, but only one finger types each letter.
• There is always a valid solution.

Thought Process

The most straightforward solution is to try every possible way to assign each letter in word to one of the two fingers, keeping track of each finger's position. However, since there are two choices for each letter and up to 300 letters, this brute-force approach would result in an exponential number of possibilities, making it infeasible for larger inputs.

To optimize, we notice that at any step, the only information we need to make an optimal decision is:

• Which letter are we about to type?
• Where are the two fingers currently located (or if they are still off the keyboard)?

This way, we avoid recomputing the same scenarios multiple times and reduce the problem to a manageable size.

Solution Approach

• Step 1: Represent the Keyboard
  Since the keyboard is a 6x5 grid, each letter's position can be calculated as (row, column) = (index // 6, index % 6), where index is the 0-based position of the letter in the alphabet.
• Step 2: Define State for DP
  Define a recursive function dp(i, f1, f2) where:
  • i: the index of the next letter to type in word
  • f1: the index in word of the last letter typed by finger 1 (or -1 if off-screen)
  • f2: the index in word of the last letter typed by finger 2 (or -1 if off-screen)
  The function returns the minimum cost to type from letter i to the end, given the current finger positions.
• Step 3: Recursive Choices
  At each step, try both options:
  • Type the i-th letter with finger 1, move finger 1 there, and recurse.
  • Type the i-th letter with finger 2, move finger 2 there, and recurse.
  For each, calculate the cost as the Manhattan distance from the previous position (if any), or 0 if from off-screen.
• Step 4: Memoization
  Use memoization (e.g., a hash map or 3D array) to cache results for each unique state to avoid recomputation.
• Step 5: Base Case
  If i reaches the end of word, return 0 (no more letters to type).
• Step 6: Initialization
  Start with both fingers off-screen (represented by -1) and begin recursion from the first letter.

This approach ensures that all possible finger assignments are considered, but redundant calculations are avoided through memoization.

Example Walkthrough

Suppose word = "CAKE".

1. Both fingers start off-screen. The first letter is 'C' (at position (0,2)). Typing with either finger costs 0.
2. Next letter is 'A' (at (0,0)). Two options:
   • Finger 1 typed 'C', so moving to 'A' costs 2 (|0-0| + |2-0|). Finger 2 is still off-screen, so could use finger 2 for 'A' with cost 0.
   The DP will consider both and pick the minimum.
3. Continue for 'K' (at (1,4)) and 'E' (at (0,4)), each time choosing the optimal finger to minimize the total distance.
4. The DP ensures that for each subproblem, the minimal cost is recorded and reused for further steps.
5. The minimum total distance for typing "CAKE" is 3.

Time and Space Complexity

• Brute-force: For each letter, two choices (which finger), so O(2ⁿ) time, which is infeasible for large word.
• Optimized DP:
  • Each state is defined by the current index and the positions of both fingers.
  • There are O(n³) possible states (n for each of i, f1, f2) because each finger can be on any previous letter or off-screen.
  • Each state does constant work, so total time and space is O(n³).

Summary

The problem is a classic example of dynamic programming with multiple state variables. By recognizing that only the current letter index and the positions of the two fingers matter, we can use memoization to efficiently explore all possible finger assignments. This reduces the complexity from exponential to cubic in the length of the word, making it practical for real-world inputs. The key insight is modeling the problem as a state machine and caching subproblem results for reuse.