<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:
        '''
        if we were to only have one finger we would have just found the distance starting from each character and see which one has the shortest distance to reach all other nodes
        
        we can place the two fingers on all letters and see what the cost would be to construct the whole string
        
        dp is possible since constraints allow for it
        
        so parameters:
        i: finger 1 starting letter
        j: finger 2 starting letter
        k: remaining letters to traverse to
        
        we have a double for loop that goes through all possible starting positions
        
        adjDict which corresponds letter to pos for calculating distance
        
        each step we choose one of i or j to change to teh next letter depending on which one is cheaper
        
        
        finger one must always be the first letter
        also we have to gin the order of the word, so finger two cant type characters unless its after it
        
        instead have x,y of both fingers if -1 we can place that finger
        so each point we have a decision to continue to use one finger or use a new finger
        if its a new finger add 0
        
        '''
        
            
        adjDict = {}
        x = 0
        
        for i in range(26):
            adjDict[chr(65 + i)] = (x, i % 6)
            
            if i % 6 == 5:
                x += 1
        
            
        def dist(first, second):
            return abs(first[0] - second[0]) + abs(first[1] - second[1])
        
        @cache        
        def dfs(i, j, a, b, ind):
            if ind == len(word):
                return 0
            
            x, y = adjDict[word[ind]]
            
            # first finger
            res = dfs(x, y, a, b, ind + 1) + (0 if i == -1 and j == -1 else abs(x - i) + abs(y - j))
            
            # second finger
            res = min(res, dfs(i, j, x, y, ind + 1) + (0 if a == -1 and b == -1 else abs(x - a) + abs(y - b)))
            
            return res
        
        return dfs(adjDict[word[0]][0], adjDict[word[0]][1], -1, -1, 1)
40200