Dew It | Tricky solution explained | Easy to understand | O(n)
APPROACH\n Imagine that we have already typed the given string upto index k\n This means that one finger is at k: this also means that the other finger is befor
**APPROACH**\n* Imagine that we have already typed the given string upto index k\n* This means that **one finger is at k**: this also means that the **other finger is before k**\n* The lagging finger could be pointing at **any one of the letters A-Z** or perhaps it was **never used at all**\n* Let us suppose that we know the optimal costs for being in any of those **27 "states"** i.e **{ A, arr[k] }, { B, arr[k] }, ... { Z, arr[k] }, { null, arr[k] }**\n(leading finger being at { arr[k] } and lagging finger last used to type { A-Z or nothing })\n* What we need is the optimal costs for reaching the 27 states when the leading finger is at { arr[k+1] } using the costs computed so far\n* The letter k+1 can be typed in one of two ways: **1. use the leading finger** VS **2. use the lagging finger**\n* If we do 2, we have a potential min cost for the state { arr[k], arr[k+1] }\nIf we do 1, we have potential min costs for { A, arr[k+1] }, { B, arr[k+1] }, ... { Z, arr[k+1] }, { null, arr[k+1] }\nNOTE: arr[k] is some char between A and Z, so there might be a clash - we take the min of the two ways from above.\n* We can **extend our logic upto n-1** and then return the lowest cost from there as the answer\n\n**CODE**\n\n```\nclass Solution {\n    public int minimumDistance(String word) {\n        int n = word.length();\n        if(n < 3) return 0;\n        \n        char[] arr = word.toCharArray();\n        int[] store = new int[27];\n        for(int i=0; i<27; ++i) store[i] = Integer.MAX_VALUE;\n        \n        store[26] = dist(arr[1], arr[0]);\n        store[arr[0]-\'A\'] = 0;\n        for(int k=2; k<n; ++k) {\n            int delta = dist(arr[k], arr[k-1]), min = store[26];\n            for(int i=0; i<27; ++i) {\n                if(store[i] < min) min = Math.min(min, store[i] + dist(arr[k], (char) (i + \'A\')));\n                if(store[i] < Integer.MAX_VALUE) store[i] += delta;\n            }\n            store[arr[k-1]-\'A\'] = Math.min(store[arr[k-1]-\'A\'], min);\n        }\n        \n        int ans = Integer.MAX_VALUE;\n        for(int x: store) ans = Math.min(ans, x);\n        \n        return ans;\n    }\n    \n    private int dist(char a, char b) {\n        int i = a - \'A\', j = b - \'A\';\n        return Math.abs(i/6 - j/6) + Math.abs(i%6 - j%6);\n    }\n}
['Java']