[Java] DP Solution, O(26*26*N) Time Complexity
\nclass Solution {\n    public int minimumDistance(String word) {\n        char[] chars = word.toCharArray();\n        int n = chars.length;\n        \n\t\t// I
```\nclass Solution {\n    public int minimumDistance(String word) {\n        char[] chars = word.toCharArray();\n        int n = chars.length;\n        \n\t\t// Initialization, dp[0][26][26] = 0\n        int[][][] dp = new int[n+1][27][27];\n        for (int i = 0; i <= n; i++) {\n            for (int j = 0; j < 27; j++) {\n                Arrays.fill(dp[i][j], Integer.MAX_VALUE/2);\n            }\n        }\n        dp[0][26][26] = 0;\n        \n        int min = Integer.MAX_VALUE;\n        for (int i = 0; i < n; i++) {\n            int index = chars[i] - \'A\';\n            for (int j = 0; j <= 26; j++) {\n                for (int k = 0; k <= 26; k++) {\n                    // left hand from k to index\n                    dp[i+1][index][j] = Math.min(dp[i+1][index][j], dp[i][k][j] + d(k, index));\n                    // right hand from k to index\n                    dp[i+1][j][index] = Math.min(dp[i+1][j][index], dp[i][j][k] + d(k, index));\n                }\n                if (i == n - 1) {\n                    min = Math.min(min, dp[i+1][index][j]);\n                    min = Math.min(min, dp[i+1][j][index]);\n                }\n            }\n        }\n        return min;\n    }\n    \n    private int d(int a, int b) {\n        if (a == 26) {\n            return 0;\n        }\n        return Math.abs(a / 6 - b / 6) + Math.abs(a % 6 - b % 6);\n    }\n}\n```
[]