Rolling Array DP O(n)
\nclass Solution:\n    def minimumDistance(self, word: str) -> int:\n        idx = lambda i: ord(word[i]) - ord(\'A\')\n        dist = lambda a, b: abs(a//6 - b
```\nclass Solution:\n    def minimumDistance(self, word: str) -> int:\n        idx = lambda i: ord(word[i]) - ord(\'A\')\n        dist = lambda a, b: abs(a//6 - b//6) + abs(a % 6 - b % 6)\n        dp = [0] * 26\n        for i in range(1, len(word)):\n            if word[i] == word[i - 1]: continue\n            ndp = [float(\'inf\')] * 26\n            for j in range(26):\n                ndp[j] = dp[j] + dist(idx(i - 1), idx(i))\n            for k in range(26):\n                ndp[idx(i - 1)] = min(ndp[idx(i - 1)], dp[k] + dist(k, idx(i)))\n            dp = ndp\n        return min(dp)\n```
[]