Solution of Keyboard

We can solve the problem using dynamic programming:

Let dp[i][L][R] = the minimum total cost of typing the first i characters, such that we end up with the left finger on the L key and the right finger on R.

Initially, dp[0]['F']['J'] = 0 and dp[everything else] = inf.
Now, assume we are in the state [i][L][R]. There are two ways of having reached this state:

• from [i-1][prevL][R], by moving the left finger from prevL to L
• from [i-1][L][prevR], by moving the right finger from prevR to R

Notice that, regardless of what we choose, one of the fingers stays in the same position.
In addition, we know that by reaching [i][L][R], we have just typed the i^th character.
As a consequence, either L or R must be equal to s[i].

Finally, we construct the following recursion:

• dp[i][s[i]][prevR] = min(dp[i][s[i]][prevR], dp[i-1][prevL][prevR] + manhattanDist[prevL][s[i]]);
• dp[i][prevL][s[i]] = min(dp[i][prevL][s[i]], dp[i-1][prevL][prevR] + manhattanDist[prevR][s[i]]);

The answer is the minimum value of dp[N][L][R], for any L, R in the alphabet.