DP solution O(n) space, 2-Dim DP , Iterative, Explained
Step 1:- [Defining the States of DP]\n\nHere state of dp is identified by the position of two fingre i.e i,j.\n\nStep 2:- [Identifing the Base Case for the solu
Step 1:- [Defining the States of DP]\n\nHere state of dp is identified by the position of two fingre i.e i,j.\n\nStep 2:- [Identifing the Base Case for the solution]\n\nFinal state will be any of dp[ i ][ n ] where 0<=i<n  and it is 0(zero) because there is no need for furthur transition  as final state is reached by typing letter at postion n which is last letter.\n\nStep 3 :- [Identifing the Relation between the dp States and framing an Equation]\n\nconsider you have solutions for state dp[ j ][  i + 1 ] where 0<=j<i+1. \n\nNow It is possible to find solution for states dp[ j ][ i ] where 0<=j<i as\n\ndp[ j ][ i ] = min( dp[ i ][ i + 1 ] + disted(j,i+1),  dp[ j ][ i + 1 ] + disted(i,i+1) );\n\nHere disted( i, j ) will be used to calculate distance between letters at position i and j respectively.\n\n1.dp[ i ][ i + 1 ] + disted(j,i+1)    :-\n\t\tfrom dp[ j ][ i ] state if finger at j is moved to i+1 position it reaches to the state dp[ i ][ i+1] (i.e one finger at position i and another finger is at position i+1)  by travelling distance of disted( j, i+1).\n\n2.dp[ j ][ i + 1 ] + disted(i,i+1)   :-\n\t\tfrom dp[ j ][ i ] state if finger at i is moved to i+1 position it reaches to the state dp[ j ][ i+1] (i.e one finger at position i and another finger is at position i+1)  by travelling distance of disted( i, i+1).\n\nAt the end dp[ j ][ i ] holds the minimum distance  to be travelled to reach the final state [i.e. answer] from the state dp[ j ][ i ].\n\n```\nclass Solution {\n    string w;\npublic:\n    int minimumDistance(string word) {\n        int n = word.size();\n        w= " "+word;\n        int dp[n+1][n+1];\n        \n        for(int i = 0 ; i < n ; i++)\n            dp[i][n] = 0;\n        \n        for(int i = n-1 ; i>0 ; i--)\n        {\n            for(int j = i-1 ; j >=0 ; j--)\n            {\n                dp[j][i] = min(dp[i][i+1]+disted(j,i+1),dp[j][i+1]+disted(i,i+1));\n            }\n            \n        }\n        return min(dp[0][1],dp[1][2]);\n     }\n    \n    int disted(int i,int j)\n    {\n        if(j==0 || i==0)return 0;\n        \n        i = w[i]-\'A\',j=w[j]-\'A\';\n        \n        return abs(i/6 - j/6) + abs(i%6 - j%6);\n    }    \n\t\n\t};\n```\n\nThe below solution is O(n) space :-\n\n```\nclass Solution {\n    string w;\npublic:\n    int minimumDistance(string word) {\n        int n = word.size();\n        w= " "+word;\n        int dp[n+1][2];\n        \n        for(int i = 0 ; i < n ; i++)\n            dp[i][n%2] = 0;\n        \n        for(int i = n-1 ; i>0 ; i--)\n        {\n            for(int j = i-1 ; j >=0 ; j--)\n            {\n                dp[j][i%2] = min(dp[i][(i+1)%2]+disted(j,i+1),dp[j][(i+1)%2]+disted(i,i+1));\n            }\n            \n        }\n        return min(dp[0][1%2],dp[1][2%2]);\n     }\n    \n    int disted(int i,int j)\n    {\n        if(j==0 || i==0)return 0;\n        \n        i = w[i]-\'A\',j=w[j]-\'A\';\n        \n        return abs(i/6 - j/6) + abs(i%6 - j%6);\n    }    \n\t\n\t};\n```\n\n\n
['Dynamic Programming', 'C', 'Iterator']