<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:
        # min distance to type a word with 2 fingers
        # keyboard with layout from left to right, top to bottom
        # 6 columns, 5 rows
        

        # given a string word, reeturn the min total distance to type such string using 2 fingers
        # distance between 2 points are abs(x1 - x2) + abs(y1 - y2)

        # 2 fingers meaning 2 starting points
        # we can divide the board down in half 
        # 0 => 2 of columns we use with left finger
        # 3 => 5 of columns we use with the right finger

        # 2 choices type the next char using either left or right finger
        # so we run dfs to find the min cost
        # without memoisation, return time is O(2 ^ n)

        # both fingers locations, and position in the input string, we have 27 locations for each finger
        # including the initial 'hovering'

        # brute force, we get all possible combination of paths to go between each char/layer
        # from the previous layer + distance from that previous char to current char
        # there are a lot of repeated work, and unnecessary works

        # 




        # create dp size len(word) x 26 x 26
        # dp[k][i][j]

        # i and j represent the left and right finger




        n = len(word)

        def distance(a, b):
            return abs(a // 6 - b // 6) + abs(a % 6 - b % 6)

        dp = [[[float('inf')] * 26 for _ in range(26)] for _ in range(n)]

        # initialize first value
        # because we can get the first char for free
        firstCharCode = ord(word[0]) - ord('A')
        for index in range(26):
            # right and left finger at first word set to 0
            dp[0][index][firstCharCode] = 0
            dp[0][firstCharCode][index] = 0

        # go through each char
        for k in range(1, n):
            index = ord(word[k]) - ord('A')

            # we move the left finger
            for i in range(26):
                for j in range(26):
                    dp[k][index][j] = min(dp[k][index][j], dp[k-1][i][j] + distance(i, index))
            
            # we move the right finger
            for i in range(26):
                for j in range(26):
                    dp[k][i][index] = min(dp[k][i][index], dp[k-1][i][j] + distance(j, index))
                
        result = float('inf')
        for i in range(26):
            for j in range(26):
                result = min(result, dp[-1][i][j])  
                # result will be the last char
                # and either finger can be on any letter?
                # that returns the min 
        
        return result
        
18800