<img alt="" src="https://assets.leetcode.com/uploads/2020/01/02/leetcode_keyboard.png" style="width: 349px; height: 209px;" />
<p>You have a keyboard layout as shown above in the <strong>X-Y</strong> plane, where each English uppercase letter is located at some coordinate.</p>

<ul>
	<li>For example, the letter <code>&#39;A&#39;</code> is located at coordinate <code>(0, 0)</code>, the letter <code>&#39;B&#39;</code> is located at coordinate <code>(0, 1)</code>, the letter <code>&#39;P&#39;</code> is located at coordinate <code>(2, 3)</code> and the letter <code>&#39;Z&#39;</code> is located at coordinate <code>(4, 1)</code>.</li>
</ul>

<p>Given the string <code>word</code>, return <em>the minimum total <strong>distance</strong> to type such string using only two fingers</em>.</p>

<p>The <strong>distance</strong> between coordinates <code>(x<sub>1</sub>, y<sub>1</sub>)</code> and <code>(x<sub>2</sub>, y<sub>2</sub>)</code> is <code>|x<sub>1</sub> - x<sub>2</sub>| + |y<sub>1</sub> - y<sub>2</sub>|</code>.</p>

<p><strong>Note</strong> that the initial positions of your two fingers are considered free so do not count towards your total distance, also your two fingers do not have to start at the first letter or the first two letters.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> word = &quot;CAKE&quot;
<strong>Output:</strong> 3
<strong>Explanation:</strong> Using two fingers, one optimal way to type &quot;CAKE&quot; is: 
Finger 1 on letter &#39;C&#39; -&gt; cost = 0 
Finger 1 on letter &#39;A&#39; -&gt; cost = Distance from letter &#39;C&#39; to letter &#39;A&#39; = 2 
Finger 2 on letter &#39;K&#39; -&gt; cost = 0 
Finger 2 on letter &#39;E&#39; -&gt; cost = Distance from letter &#39;K&#39; to letter &#39;E&#39; = 1 
Total distance = 3
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> word = &quot;HAPPY&quot;
<strong>Output:</strong> 6
<strong>Explanation:</strong> Using two fingers, one optimal way to type &quot;HAPPY&quot; is:
Finger 1 on letter &#39;H&#39; -&gt; cost = 0
Finger 1 on letter &#39;A&#39; -&gt; cost = Distance from letter &#39;H&#39; to letter &#39;A&#39; = 2
Finger 2 on letter &#39;P&#39; -&gt; cost = 0
Finger 2 on letter &#39;P&#39; -&gt; cost = Distance from letter &#39;P&#39; to letter &#39;P&#39; = 0
Finger 1 on letter &#39;Y&#39; -&gt; cost = Distance from letter &#39;A&#39; to letter &#39;Y&#39; = 4
Total distance = 6
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= word.length &lt;= 300</code></li>
	<li><code>word</code> consists of uppercase English letters.</li>
</ul>

class Solution:
    def minimumDistance(self, word: str) -> int:
        # Initialize the coordinates of each letter
        coords = {}
        for i in range(26):
            coords[chr(ord('A') + i)] = (i // 6, i % 6)
        
        # Function to calculate the distance between two points
        def dist(p1, p2):
            return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])
        
        # Initialize the DP table
        n = len(word)
        dp = [[[float('inf')] * 27 for _ in range(27)] for _ in range(n + 1)]
        
        # Base case: when no characters are left, the distance is 0
        for i in range(27):
            for j in range(27):
                dp[n][i][j] = 0
        
        # Fill the DP table
        for i in range(n - 1, -1, -1):
            for j in range(27):  # Position of the first finger
                for k in range(27):  # Position of the second finger
                    next_char = ord(word[i]) - ord('A')
                    # Move the first finger
                    dp[i][j][k] = min(dp[i][j][k], dp[i + 1][next_char][k] + dist(coords[word[i]], coords.get(chr(ord('A') + j), (0, 0))))
                    # Move the second finger
                    dp[i][j][k] = min(dp[i][j][k], dp[i + 1][j][next_char] + dist(coords[word[i]], coords.get(chr(ord('A') + k), (0, 0))))
        
        # The answer is the minimum distance when both fingers start at any position
        return min(dp[0][j][k] for j in range(27) for k in range(27))

# Example usage:
solution = Solution()
print(solution.minimumDistance("CAKE"))  # Output: 3
print(solution.minimumDistance("HAPPY"))  # Output: 6
22700