2ms Java DP O(N) in time
//  left[i] : so far the optimal result if previous char tapped by the left finger, and the last char tapped by the right finger is \'A\' + i   \n// At each pos
//  left[i] : so far the optimal result if previous char tapped by the left finger, and the last char tapped by the right finger is \'A\' + i   \n// At each position, there are two options either keep using the left finger, or switch from right finger to left finger\n// Due to symmetry, if right[] is created as left[], we have right[i] = left[i] for all i. We may only consider left[], and ignore right[]\n```\nclass Solution {\n    public int minimumDistance(String word) {      \n        int[][] dist = new int[26][26];\n        for (int i=0; i<26; ++i) {\n            for (int j=i; j<26; ++j) {\n                dist[i][j] = Math.abs(i / 6 - j / 6) + Math.abs(i % 6 - j % 6);\n                dist[j][i] = dist[i][j];\n            }\n        }       \n        int[] left = new int[26];  \n\t\t//left[i] : so far the optimal result if previous char tapped by the left finger, and last char by right finger is \'A\' + i        \n        for (int i=1; i<word.length(); ++i) {\n            int preIdx = word.charAt(i-1) - \'A\', curIdx = word.charAt(i) - \'A\';\n            int rightToLeft = Integer.MAX_VALUE;\n            for (int j=0; j<26; ++j) {\n\t\t\t   //previous char use right finger, while current char use left finger. \n\t\t\t   //It should be right[j] + dist[j][curIdx], however we have left[j] = right[j] due to symmetry\n                rightToLeft = Math.min(rightToLeft, left[j] + dist[j][curIdx]);  \n            }\n            for (int j=0; j<26; ++j) {\n                left[j] += dist[preIdx][curIdx]; //previous char using left finger, and so does current char\n            }\n            left[preIdx] = Math.min(left[preIdx], rightToLeft);\n        }\n        int count = Integer.MAX_VALUE;\n        for (int i=0; i<26; ++i) {\n            count = Math.min(count, left[i]);\n        }\n        return count;\n    }\n}\n```
[]