<p>In the video game Fallout 4, the quest <strong>&quot;Road to Freedom&quot;</strong> requires players to reach a metal dial called the <strong>&quot;Freedom Trail Ring&quot;</strong> and use the dial to spell a specific keyword to open the door.</p>

<p>Given a string <code>ring</code> that represents the code engraved on the outer ring and another string <code>key</code> that represents the keyword that needs to be spelled, return <em>the minimum number of steps to spell all the characters in the keyword</em>.</p>

<p>Initially, the first character of the ring is aligned at the <code>&quot;12:00&quot;</code> direction. You should spell all the characters in <code>key</code> one by one by rotating <code>ring</code> clockwise or anticlockwise to make each character of the string key aligned at the <code>&quot;12:00&quot;</code> direction and then by pressing the center button.</p>

<p>At the stage of rotating the ring to spell the key character <code>key[i]</code>:</p>

<ol>
	<li>You can rotate the ring clockwise or anticlockwise by one place, which counts as <strong>one step</strong>. The final purpose of the rotation is to align one of <code>ring</code>&#39;s characters at the <code>&quot;12:00&quot;</code> direction, where this character must equal <code>key[i]</code>.</li>
	<li>If the character <code>key[i]</code> has been aligned at the <code>&quot;12:00&quot;</code> direction, press the center button to spell, which also counts as <strong>one step</strong>. After the pressing, you could begin to spell the next character in the key (next stage). Otherwise, you have finished all the spelling.</li>
</ol>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img src="https://assets.leetcode.com/uploads/2018/10/22/ring.jpg" style="width: 450px; height: 450px;" />
<pre>
<strong>Input:</strong> ring = &quot;godding&quot;, key = &quot;gd&quot;
<strong>Output:</strong> 4
<strong>Explanation:</strong>
For the first key character &#39;g&#39;, since it is already in place, we just need 1 step to spell this character. 
For the second key character &#39;d&#39;, we need to rotate the ring &quot;godding&quot; anticlockwise by two steps to make it become &quot;ddinggo&quot;.
Also, we need 1 more step for spelling.
So the final output is 4.
</pre>

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

<pre>
<strong>Input:</strong> ring = &quot;godding&quot;, key = &quot;godding&quot;
<strong>Output:</strong> 13
</pre>

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

<ul>
	<li><code>1 &lt;= ring.length, key.length &lt;= 100</code></li>
	<li><code>ring</code> and <code>key</code> consist of only lower case English letters.</li>
	<li>It is guaranteed that <code>key</code> could always be spelled by rotating <code>ring</code>.</li>
</ul>

class Solution:
    def findRotateSteps(self, ring: str, key: str) -> int:

        """
        Approach: BFS with priority queue (steps_taken: int, remaining_chars: str, cur_idx: int)
        
        The priority is determined based on the steps taken so far.

        For the next character c in the key (key[0]), find the minimum distance from the current index
        to the index of c and add to priority queue. If there are multiple char c in the ring, add all 
        to the priority queue. Make sure to keep track of already visited remaining_chars and idx to
        prevent duplicate processing.
        """

        # Create a dictionary to store the indices of each character in the ring
        char_indices = defaultdict(list)
        for i, c in enumerate(ring):
            char_indices[c].append(i)

        # Initialize the priority queue with the starting point: (steps_taken, remaining_chars, idx_of_12:00_char)
        queue = [(0, key, 0)]
        n = len(ring)
        visited = set()

        while queue:
            # Get the element with the least steps taken
            steps_taken, remaining_chars, idx = heapq.heappop(queue)
            
            # If there are no remaining characters in the key, return the steps taken
            if not remaining_chars:
                return steps_taken
            
            # Skip if this state has been visited already
            if (remaining_chars, idx) in visited:
                continue
            visited.add((remaining_chars, idx))
            
            # If the current character at ring[idx] matches the next character in the key
            if ring[idx] == remaining_chars[0]:
                # Push the new state to the queue with the steps incremented by 1 and the next character in the key
                heapq.heappush(queue, (steps_taken + 1, remaining_chars[1:], idx))
                continue
            
            # For each index of the next character in the key
            for target_idx in char_indices[remaining_chars[0]]:
                # Calculate the distance in both clockwise and counterclockwise directions
                distance = abs(target_idx - idx)
                min_distance = min(distance, len(ring) - distance)
                
                # Push the new state to the queue with the updated steps and index
                heapq.heappush(queue, (steps_taken + min_distance + 1, remaining_chars[1:], target_idx))
        
        # If the loop completes without returning, return -1 indicating failure (although theoretically unreachable)
        return -1

        

        # My Original Approach: BFS with a DFS to find the closest next matching char
        # Tracked the current direction and only expanded search (check both turns) when you run into a match
        # Otherwise, you stay going the same path. 
        # This was kind of the same approach, but it did not need a PQ because it was technically a BFS and 
        # it was manually doing a dfs to the next target characters index rather than computing the distance
        # and jumping there automatically
        # Time failed obviously

        # queue = collections.deque([(0, key, 0, None)]) # steps_taken, remaining_chars, idx_of_12:00_char, last_direction
        # n = len(ring)

        # while queue:
        #     steps_taken, remaining_chars, idx, direction = queue.popleft()
        #     if not remaining_chars:
        #         return steps_taken
        #     if ring[idx] == remaining_chars[0]:
        #         queue.append((steps_taken + 1, remaining_chars[1:], idx, None))
        #         continue
        #     if not direction:
        #         queue.append((steps_taken + 1, remaining_chars, (idx+1) % n, 1))
        #         queue.append((steps_taken + 1, remaining_chars, (idx-1) % n, -1))
        #     else:
        #         queue.append((steps_taken + 1, remaining_chars, (idx+direction) % n, direction))
17100