Minimum Distance to Type a Word Using Two Fingers solution and explanation

def minimumDistance(word):
    def get_pos(ch):
        row = (ord(ch) - ord('A')) // 6
        col = (ord(ch) - ord('A')) % 6
        return (row, col)

    def dist(pos1, pos2):
        return abs(pos1[0] - pos2[0]) + abs(pos1[1] - pos2[1])

    n = len(word)
    dp = {}

    def dp_solve(i, f1, f2):
        if i == n:
            return 0
        if (i, f1, f2) in dp:
            return dp[(i, f1, f2)]
        pos_curr = get_pos(word[i])
        pos_f1 = get_pos(f1) if f1 else None
        pos_f2 = get_pos(f2) if f2 else None
        cost_f1 = dist(pos_f1, pos_curr) if pos_f1 else 0
        cost_f2 = dist(pos_f2, pos_curr) if pos_f2 else 0
        use_f1 = dp_solve(i + 1, word[i], f2) + cost_f1
        use_f2 = dp_solve(i + 1, f1, word[i]) + cost_f2
        dp[(i, f1, f2)] = min(use_f1, use_f2)
        return dp[(i, f1, f2)]

    return dp_solve(0, None, None)

function minimumDistance(word) {
    const getPos = (ch) => [Math.floor((ch.charCodeAt(0) - 'A'.charCodeAt(0)) / 6), (ch.charCodeAt(0) - 'A'.charCodeAt(0)) % 6];
    const dist = (pos1, pos2) => Math.abs(pos1[0] - pos2[0]) + Math.abs(pos1[1] - pos2[1]);
    const dp = new Map();

    const dp_solve = (i, f1, f2) => {
        if (i === word.length) return 0;
        const key = `${i}-${f1}-${f2}`;
        if (dp.has(key)) return dp.get(key);
        const posCurr = getPos(word[i]);
        const posF1 = f1 ? getPos(f1) : null;
        const posF2 = f2 ? getPos(f2) : null;
        const costF1 = posF1 ? dist(posF1, posCurr) : 0;
        const costF2 = posF2 ? dist(posF2, posCurr) : 0;
        const useF1 = dp_solve(i + 1, word[i], f2) + costF1;
        const useF2 = dp_solve(i + 1, f1, word[i]) + costF2;
        const result = Math.min(useF1, useF2);
        dp.set(key, result);
        return result;
    };

    return dp_solve(0, null, null);
}

class Solution {
    public int minimumDistance(String word) {
        int n = word.length();
        int[][] dp = new int[n][26];
        for (int[] row : dp)
            Arrays.fill(row, Integer.MAX_VALUE);
        dp[0][word.charAt(0) - 'A'] = 0;

        for (int i = 1; i < n; ++i) {
            int curr = word.charAt(i) - 'A';
            for (int j = 0; j < 26; ++j) {
                dp[i][curr] = Math.min(dp[i][curr], dp[i - 1][j] + dist(j, curr));
                dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + dist(word.charAt(i - 1) - 'A', curr));
            }
        }

        return Arrays.stream(dp[n - 1]).min().getAsInt();
    }

    private int dist(int a, int b) {
        if (a == -1) return 0;
        return Math.abs(a / 6 - b / 6) + Math.abs(a % 6 - b % 6);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.minimumDistance("CAKE")); // Output: 3
    }
}

#include <iostream>
#include <vector>
#include <cmath>
#include <climits>
using namespace std;

int minimumDistance(string word) {
    auto dist = [](int a, int b) {
        if (a == -1) return 0;
        return abs(a / 6 - b / 6) + abs(a % 6 - b % 6);
    };

    int n = word.length();
    vector<vector<int>> dp(n, vector<int>(26, INT_MAX));
    dp[0][word[0] - 'A'] = 0;

    for (int i = 1; i < n; ++i) {
        int curr = word[i] - 'A';
        for (int j = 0; j < 26; ++j) {
            dp[i][curr] = min(dp[i][curr], dp[i-1][j] + dist(j, curr));
            dp[i][j] = min(dp[i][j], dp[i-1][j] + dist(word[i-1] - 'A', curr));
        }
    }
    return *min_element(dp[n - 1].begin(), dp[n - 1].end());
}

int main() {
    cout << minimumDistance("CAKE") << endl; // Output: 3
    return 0;
}

func minimumDistance(word string) int {
	n := len(word)
	f := make([][26][26]int, n)
	const inf = 1 << 30
	for i := range f {
		for j := range f[i] {
			for k := range f[i][j] {
				f[i][j][k] = inf
			}
		}
	}
	for j := range f[0] {
		f[0][word[0]-'A'][j] = 0
		f[0][j][word[0]-'A'] = 0
	}
	dist := func(a, b int) int {
		x1, y1 := a/6, a%6
		x2, y2 := b/6, b%6
		return abs(x1-x2) + abs(y1-y2)
	}
	for i := 1; i < n; i++ {
		a, b := int(word[i-1]-'A'), int(word[i]-'A')
		d := dist(a, b)
		for j := 0; j < 26; j++ {
			f[i][b][j] = min(f[i][b][j], f[i-1][a][j]+d)
			f[i][j][b] = min(f[i][j][b], f[i-1][j][a]+d)
			if j == a {
				for k := 0; k < 26; k++ {
					t := dist(k, b)
					f[i][b][j] = min(f[i][b][j], f[i-1][k][a]+t)
					f[i][j][b] = min(f[i][j][b], f[i-1][a][k]+t)
				}
			}
		}
	}
	ans := inf
	for j := 0; j < 26; j++ {
		ans = min(ans, f[n-1][word[n-1]-'A'][j])
		ans = min(ans, f[n-1][j][word[n-1]-'A'])
	}
	return ans
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}