C++ 8ms 1D DP solution w/ detailed explanation
This is a different solution compared to the official, which is lee215\'s solution 2. I spent 2 hours and could not understand how that solution works. However,
This is a different solution compared to the official, which is lee215\'s solution 2. I spent 2 hours and could not understand how that solution works. However, using that as a reference I was able to come up with my own solution that runs in `O(K*N)`, where `N = word.size()`. and `K = alphabet.size()`. \n\n**Approach:**\n\nThe idea for this solution is based on the observation that **right before we press character at index `i`, a finger must be on index \'i-1\'**. Now there are two fingers, which we can label as `one` and `two`. We can use this to further define the previously stated condition as:\n\n**At index `i`, either `one` or `two` must be at `i-1`.**\n\nIn order to proceed, we need to press character at `i`. Let\'s look at all the possible scenarios that could play out:\n\n1. We used `one` to press `i-1`. We can press `i` with `one` again, while `two` stays unchanged at its index.\n2. We used `one` to press `i-1`. We can press `i` with `two`. Now `one` stays at `i-1`, while `two` moves from its previous index to `i`.\n3. We used `two` to press `i-1`. We can press `i` with `two` again, while `one` stays unchanged at its index.\n4. We used `two` to press `i-1`. We can press `i` with `one`. Now `two` stays at `i-1`, while `one` moves from its previous index to `i`.\n\nWe can use these to build the transition for the DP algorithm.\n\nBecause a finger must be at index `i-1`, we can define our DP state as follows:\n\n`one[j]: ` The minimum cost required to have finger `one` on current character, while finger `two` is on some other index with character index `j`. Character index is just index of character in the alphabet, so `A = 0`, `B = 1`, etc.\n\n`two[j]: ` The minimum cost required to have finger `one` on current character, while finger `one` is on some other index with character index `j`. \n\nEssentially these two arrays contains the minimum cost to have the *other* finger at a particular character index. \n\nUsing the 4 possible scenarios, we can define the update function as:\n\n`newOne[j] = min(one[j] + dist(cur, last)`\n`newTwo[j] = min(two[j] + dist(cur, last)`\n\nwhere `dist` is the function calculating distance between two characters, `cur` is character index of current character (index `i`), and `last` is character index of the previous character (index `i-1`).\n\nBut we are not done. The updates previously only covers scenario 1 and 3. Scenario 2 and 4 are a bit different. *They only update `last` in the other finger\'s state*. This is because say we have scenario 2. We move `two` to `i`. We can figure out the minimum cost to do that. However, we need to use this to update `one`\'s cost at `last`, since our new state is `two` at `i` and `one` staying at `last`. So we want to update `last` of `two`. It is the opposite for scenario 4. \n\n`newOne[last] = min(newOne[last], min_k(two[k] + dist(cur, k)`\n`newTwo[last] = min(newOne[last], min_k(one[k] + dist(cur, k)` \n\nwhere `min_k(two[k], dist(cur, k))` is the minimum value we can get by moving the second finger while first finger is on `i-1`, and similarly for `min_k(one[k], dist(cur, k))`. `one` and `two` contain all possible positions of the *other* finger while itself is on `i-1`, so to find the lowest cost to move the other finger to `i`, we need to check them all.\n\nIf we look at the two update steps, they are both `O(K)`, `K` being size of the alphabet. Thus, the run-time required to calculate `one[N-1]` and `two[N-1]` is `O(N*K)`, which is the run-time for this algorithm. Space complexity is `O(K)`. \n\nTo get the solution, we look for the minimum state in `one` or `two`, since by definition `one[N-1]` and `two[N-1]` means the minimum cost having pressed character using either finger at index `N-1`, which means we have pressed all characters.\n\n**Code**\n```\nclass Solution {\npublic:\n    int minimumDistance(const string& word) {\n        int size = word.size();\n        if(size <= 2) return 0;\n        \n        auto dist = [](int a, int b) {\n            if(a == 26) return 0;\n            return abs(a/6 - b/6) + abs(a % 6 - b % 6);\n        };\n        \n        vector<int> one(27, 9001), two(27, 9001);\n        one[26] = 0;\n        two[26] = 0;\n        for(int i = 1; i < size; ++i) {\n            vector<int> t1(27, 0), t2(27, 0);\n            int last = word[i-1] - \'A\', cur = word[i] - \'A\';\n            for(int j = 0; j <= 26; ++j) { // Update for scenario 1, 3\n                t1[j] = one[j] + dist(last, cur);\n                t2[j] = two[j] + dist(last, cur);\n            }\n            int min1 = 9001, min2 = 9001;\n            for(int j = 0; j <= 26; ++j) { // Update for scenario 2, 4\n                min1 = min(min1, two[j] + dist(j, cur));\n                min2 = min(min2, one[j] + dist(j, cur));\n            }\n            t1[last] = min(t1[last], min1);\n            t2[last] = min(t2[last], min2);\n            one = t1;\n            two = t2;\n        }\n        \n        int min_ = 9001;\n        for(int i = 0; i <= 26; ++i) { // Get minimum of using either one or two to press last character\n            min_ = min(min_, min(one[i], two[i]));\n        }\n        return min_;\n    }\n};\n\nauto gucciGang = []() {std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();\n```
[]