In this problem, we have 2 finger **left** and **right**. For each character,
we could use either **left** finder or **right** finger to push the key. Since
the number of characters is 2 - 300, there are totally 2 ^ 300 possible
situations. So the brute force solution would failed with
*Time Limit Exceeded*.

Now let's consider solving it using DP. For each character in the given string, there are several possible states where each finger is located on one position. For next character, we could get 2 possible states from every current state.

For example, state DP[i][x][y] is the minimum cost for solving string s[:i] and left finger on x and right finger on y. Then DP[i + 1][m][n] is the minimum value of DP[i][x][y] + distance(x, y, m, n) for all possible x and y.

```
import string
class Solution:
ROW = 6
def index(self, c):
return ord(c) - ord('A')
def coordinate(self, index):
return index % self.ROW, index // self.ROW
def distance(self, i, j):
x1, y1 = self.coordinate(i)
x2, y2 = self.coordinate(j)
return abs(x1 - x2) + abs(y1 - y2)
def minimumDistance(self, word: str) -> int:
distance = {}
for i in range(26):
for j in range(26):
distance[(i, j)] = 0
for c in word:
index = self.index(c)
tmp = {}
for (i, j), v in distance.items():
if (i, index) not in tmp:
tmp[(i, index)] = v + self.distance(j, index)
else:
tmp[(i, index)] = min(
tmp[(i, index)],
v + self.distance(j, index)
)
if (index, j) not in tmp:
tmp[(index, j)] = v + self.distance(i, index)
else:
tmp[(index, j)] = min(
tmp[(index, j)],
v + self.distance(i, index)
)
distance = tmp
return min(distance.values())
```