Freedom Trail

class Solution {
public:
    int rotateSteps(string ring, string key) {
        int lenRing = ring.size();
        int lenKey = key.size();

        // Map to store positions of each character in the ring
        unordered_map<char, vector<int>> indexMap;
        for (int i = 0; i < ring.size(); i++) {
            char c = ring[i];
            indexMap[c].push_back(i);
        }

        // Min-heap to explore minimum steps first
        priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> minHeap;
        minHeap.push({0, 0, 0});

        // Set to track the visited {ring position, key index}
        unordered_set<string> visited;

        // Processing the heap to find the minimum rotation steps
        int minSteps = 0;
        while (!minHeap.empty()) {
            vector<int> current = minHeap.top();
            minHeap.pop();
            minSteps = current[0];
            int currentIndex = current[1];
            int currentKeyIndex = current[2];

            // If we have spelled the entire key
            if (currentKeyIndex == lenKey) {
                break;
            }

            string visitKey = to_string(currentIndex) + "-" + to_string(currentKeyIndex);
            if (visited.find(visitKey) != visited.end()) {
                continue;
            }

            // Marking the state as visited
            visited.insert(visitKey);

            // Traverse the visible states and push them to the heap
            for (int newIndex : indexMap[key[currentKeyIndex]]) {
                minHeap.push({minSteps + getMinSteps(currentIndex, newIndex, lenRing),
                              newIndex, currentKeyIndex + 1});
            }
        }

        return minSteps + lenKey;
    }

private:
    // Helper function to calculate minimal rotation steps between two indices
    int getMinSteps(int start, int dest, int length) {
        int direct = abs(start - dest);
        int reverse = length - direct;
        return min(direct, reverse);
    }
};

class Solution {
    public int calculateSteps(String dial, String target) {
        int dialSize = dial.length();
        int targetLength = target.length();

        // Map to hold character positions in the dial
        Map<Character, List<Integer>> characterLocations = new HashMap<>();
        for (int i = 0; i < dialSize; i++) {
            char charAtPos = dial.charAt(i);
            characterLocations.computeIfAbsent(charAtPos, x -> new ArrayList<>()).add(i);
        }

        // Priority queue to manage states during exploration
        PriorityQueue<int[]> statesQueue = new PriorityQueue<>(Comparator.comparingInt(s -> s[0]));
        statesQueue.add(new int[] {0, 0, 0});

        // Set to track visited states
        Set<Pair<Integer, Integer>> visited = new HashSet<>();

        int minSteps = 0;
        while (!statesQueue.isEmpty()) {
            int[] currentState = statesQueue.poll();
            minSteps = currentState[0];
            int currentDialIndex = currentState[1];
            int targetIndex = currentState[2];

            if (targetIndex == targetLength) {
                break;
            }

            Pair<Integer, Integer> stateKey = new Pair<>(currentDialIndex, targetIndex);
            if (visited.contains(stateKey)) {
                continue;
            }

            visited.add(stateKey);
            
            char targetChar = target.charAt(targetIndex);
            for (int newIndex : characterLocations.get(targetChar)) {
                int steps = minSteps + getDistance(currentDialIndex, newIndex, dialSize);
                statesQueue.offer(new int[] {steps, newIndex, targetIndex + 1});
            }
        }

        return minSteps + targetLength; 
    }

    private int getDistance(int startIndex, int endIndex, int totalLength) {
        int directDistance = Math.abs(startIndex - endIndex);
        return Math.min(directDistance, totalLength - directDistance);
    }
}

class Solution:
    def minimumRotateSteps(self, dial_str: str, target_str: str) -> int:
        dial_length = len(dial_str)
        target_length = len(target_str)

        # Helper function to calculate minimum step difference
        def calc_steps(start, end):
            diff = abs(start - end)
            alt_diff = dial_length - diff
            return min(diff, alt_diff)

        # Store indices where each character appears in the dial
        char_locations = collections.defaultdict(list)
        for idx, c in enumerate(dial_str):
            char_locations[c].append(idx)

        # Min-heap priority queue initialization with tuple (total_moves, current_position, target_char_index)
        priority_queue = [(0, 0, 0)]
        visited_states = set()

        # Process to perform dialing to reach the target sequence
        while priority_queue:
            current_steps, current_index, target_index = heapq.heappop(priority_queue)

            # Check if complete target sequence is matched
            if target_index == target_length:
                break

            if (current_index, target_index) in visited_states:
                continue

            # Mark the current state as visited
            visited_states.add((current_index, target_index))

            # Push new states into the heap
            for new_position in char_locations[target_str[target_index]]:
                new_steps = current_steps + calc_steps(current_index, new_position) + 1
                heapq.heappush(priority_queue, (new_steps, new_position, target_index + 1))

        # Return the total number of moves made including key presses
        return current_steps + target_length