[Java/C++/Python] 1D DP, O(1) Space
Solution 1: 2D DP\n1. Initial the position of two fingers as (0,0).\n2. Iterate the input sttring and track the position of two fingers after tap the last chara
## **Solution 1: 2D DP**\n1. Initial the position of two fingers as `(0,0)`.\n2. Iterate the input sttring and track the position of two fingers after tap the last character.\n3. `dp[a,b]` means with one finger at `a` and the other at postion `b`,\nthe minimum distance we need is `dp[a, b]`.\n4. `d(a, b)` return the distance moving from `a` to `b`. Also if `a = 0` we return `0`.\n<br>\n\n## **Complexity**\nTime `O(N)`\nSpace `O(1)`\n<br>\n\n**Python:**\n```python\n    def minimumDistance(self, A):\n        def d(a, b):\n            return a and abs(a / 6 - b / 6) + abs(a % 6 - b % 6)\n\n        dp, dp2 = {(0, 0): 0}, {}\n        for c in (ord(c) + 1 for c in A):\n            for a, b in dp:\n                dp2[c, b] = min(dp2.get((c, b), 3000), dp[a, b] + d(a, c))\n                dp2[a, c] = min(dp2.get((a, c), 3000), dp[a, b] + d(b, c))\n            dp, dp2 = dp2, {}\n        return min(dp.values())\n```\n<br>\n\n## **Solution 2: 1D DP**\n3 dimensions is absolutely super easy to understand.\nThough for me is not easy to write (hate to brackets).\n\n2 dimension dynamic programming is a good optimisation and not hard to come up with.\nBy 2 dimension, I mean to recorde the positions of both fingers.\n\nBut either 2D or 3D, We actually don\'t really need at all.\nWe only need to record the position of the left finger.\n\nOne important observation is that,\nout right finger will always stay at `A[i - 1]` after the last move.\n\nThis is key idea that I want to express in this solution.\n<br>\n\n\n## **Explanation**\nImagine that we tap all letters with only one finger.\nThe `res` distance we get is the maximum distance we will need.\n\nIn our dynamic programming, `dp[a]` means that,\nif our left finger ends at character `a`,\nthe maximum we can save is `dp[a]`.\n\n\nNow our right finger tapped all letters, and left finger did nothing.\nWe iterate through the whole string one by one\nand select some letter to tap with the left finger.\nBy doing this, we want to find out the maximum distance that we can save from the tapping with one finger.\n\nAssume that our left finger is at `a` now,\nour right finger is at `b`,\nand we the right finger will tap `c` next.\n\nInstead of moving right finger from `b` to `c` with distance `d(b, c)`,\nwe try moving left finger from `a` to `c` with distance `d(a, c)`.\nHopely this will save `d(b, c) - d(a, c)`.\n\nAnd finaly, we have one fingers at `b` and the other at `c` now.\nThe finger at `b` will be new left finger, and the other will be the rihgt.\n<br>\n\n**Java**\n```java\n    public int minimumDistance(String word) {\n        int dp[] = new int[26], res = 0, save = 0, n = word.length();\n        for (int i = 0; i < n - 1; ++i) {\n            int b = word.charAt(i) - \'A\', c = word.charAt(i + 1) - \'A\';\n            for (int a = 0; a < 26; ++a)\n                dp[b] = Math.max(dp[b], dp[a] + d(b, c) - d(a, c));\n            save = Math.max(save, dp[b]);\n            res += d(b, c);\n        }\n        return res - save;\n\n    }\n\n    private int d(int a, int b) {\n        return Math.abs(a / 6 - b / 6) + Math.abs(a % 6 - b % 6);\n    }\n```\n\n**C++**\n```cpp\n    int minimumDistance(string word) {\n        vector<int> dp(26);\n        int res = 0, save = 0, n = word.size();\n        for (int i = 0; i < n - 1; ++i) {\n            int b = word[i] - \'A\', c = word[i + 1] - \'A\';\n            for (int a = 0; a < 26; ++a)\n                dp[b] = max(dp[b], dp[a] + d(b, c) - d(a, c));\n            save = max(save, dp[b]);\n            res += d(b, c);\n        }\n        return res - save;\n    }\n\n    int d(int a, int b) {\n        return abs(a / 6 - b / 6) + abs(a % 6 - b % 6);\n    }\n```\n\n**Python**\nThe following Python solution takes `O(N)`space actually,\nbut I\'d like to keep it simple now.\n```py\n    def minimumDistance(self, A):\n        def d(a, b):\n            return abs(a / 6 - b / 6) + abs(a % 6 - b % 6)\n        A = [ord(c) - 65 for c in A]\n        dp = [0] * 26\n        for b, c in zip(A, A[1:]):\n            dp[b] = max(dp[a] + d(b, c) - d(a, c) for a in xrange(26))\n        return sum(d(b, c) for b, c in zip(A, A[1:])) - max(dp)\n```\n<br>\n\n\n## **Intuition**\nPeople keep asking me how I think when solve the problem.\nThis one of the hardest question that I come across.\nIt\'s always the part I try to fill in every my post.\nThat is also one of reason it worth being upvoted for:\nI really try to explain the idea well (though it\'s not always easy and people help me).\n\nHonestly, doing same-looking prolems doesn\'t help im my case at all.\nActually I want to say that use the imagination.\nThis problem is good chance to explain.\n(Well, practice does make perfect. I hope after one year I do improve in writing my posts.)\n<br>\n\n## **Better Explantion with Imagination**\nAs in this problem, I imagine it as a problem of **linked list**:\n\nEach node has a character as ite value.\nThe distance between two linked node is same as descriped in the statament.\n\nNow we are given a linked list, we want split the it into two linked list,\nbut keep the order of nodes in each list as it in the original input.\n\nSo we need split some nodes from the original long linked list,\nand like them into the other one.\n`dp[a]` means that the last node in the second list has value `a` and save distance `dp[a]`.\n\nIn my solution, I initialized a dummy node on the left first.\nThen iterate the long linked list one by one.\n\nAssume the short linked list is `xxxa` and the long linked list is `xxxxbcxxxxx`.\nWe try cutting the link between `b` and `c`, and link it the short one.\nNow we have `xxxacxxxxxx` and `xxxxb`.\nWe compare the distance we save `d(b, c) - d(a, c)`.\nNote that `xxxxb` become the second linked list now,\nsince we think the first one always has the tail of input.\n\nFinally,\nWe compare the distance we save\nand update it to `dp[b] = max(dp[b], dp[a] + d(b, c) - d(a, c))`.\n\nThat is it.\n<br>
[]