In the video game Fallout 4, the quest "Road to Freedom" requires players to reach a metal dial called the "Freedom Trail Ring" and use the dial to spell a specific keyword to open the door.
Given a string ring that represents the code engraved on the outer ring and another string key that represents the keyword that needs to be spelled, return the minimum number of steps to spell all the characters in the keyword.
Initially, the first character of the ring is aligned at the "12:00" direction. You should spell all the characters in key one by one by rotating ring clockwise or anticlockwise to make each character of the string key aligned at the "12:00" direction and then by pressing the center button.
At the stage of rotating the ring to spell the key character key[i]:
ring's characters at the "12:00" direction, where this character must equal key[i].key[i] has been aligned at the "12:00" direction, press the center button to spell, which also counts as one step. After the pressing, you could begin to spell the next character in the key (next stage). Otherwise, you have finished all the spelling.
Example 1:
Input: ring = "godding", key = "gd" Output: 4 Explanation: For the first key character 'g', since it is already in place, we just need 1 step to spell this character. For the second key character 'd', we need to rotate the ring "godding" anticlockwise by two steps to make it become "ddinggo". Also, we need 1 more step for spelling. So the final output is 4.
Example 2:
Input: ring = "godding", key = "godding" Output: 13
Constraints:
1 <= ring.length, key.length <= 100ring and key consist of only lower case English letters.key could always be spelled by rotating ring.Problem Overview: You are given a circular ring with characters engraved on it and a target key. Rotating the ring left or right moves characters under the pointer, and pressing the center selects the current character. Each rotation step and button press counts as one move. The goal is to compute the minimum number of steps required to spell the entire key.
Approach 1: Dynamic Programming with Memoization (O(m * n * k) time, O(m * n) space)
Preprocess the ring by mapping each character to all indices where it appears. For each position in the key, you try every ring index that matches that character. The cost is the minimum rotation distance between the current pointer and the target index plus one step for pressing the button. Use recursion with memoization where the state is (keyIndex, ringPosition). The memo table avoids recomputing subproblems and drastically reduces the search space. This approach works well because the ring length is small and repeated characters allow multiple candidate transitions.
The key insight is that the optimal solution depends only on the current ring pointer and the next character you need. For each candidate index, compute the rotation cost using min(abs(a-b), n-abs(a-b)). This is a classic state transition problem that fits naturally into dynamic programming with recursion similar to problems involving circular movement and string transitions.
Approach 2: Breadth-First Search on Ring States (O(m * n * k) time, O(n) space)
Model the ring as a state graph where each node represents a pointer position. Starting from position 0, perform level-based exploration to match the next character in the key. For each key character, transition to all ring indices containing that character and compute the minimal rotation cost from the current positions. BFS keeps track of the minimal cost to reach each position after processing a prefix of the key.
This approach treats the problem like shortest-path traversal over ring states. Instead of recursion, it iteratively expands possible pointer locations after spelling each character. The main operations include iterating over candidate indices and updating the minimal cost using rotation distance. BFS can be easier to reason about if you think of the ring as a graph and want a non-recursive solution using breadth-first search.
Recommended for interviews: Dynamic Programming with memoization is the expected solution. It demonstrates strong state modeling, optimal substructure recognition, and efficient pruning of repeated work. BFS shows a valid graph perspective, but interviewers usually prefer the DP formulation because it clearly expresses the transition between ring positions and key indices while leveraging string indexing.
In this approach, we'll use a recursive solution with memoization to efficiently calculate the minimum number of steps. The function will take the current position in the ring and the current index in the key string as parameters, and will calculate the optimal steps required for each character. We'll cache the results of subproblems to avoid recalculating them.
This solution defines a recursive function `dp` that returns the minimum steps from a given position `pos` in the ring to spell the remainder of the `key` starting from index `idx`. We use a hashmap `ring_indices` to find all positions in the `ring` that match the current character of `key`. For each potential position, we calculate the number of steps required to reach it from the current position, both clockwise and counter-clockwise, and add 1 for the press action. We store the solution in a memoization table to prevent recalculation.
Time Complexity: O(m*n), where m is the length of the `key` and n is the length of the `ring`.
Space Complexity: O(m*n) for the memoization table and index dictionary.
In this approach, we'll leverage BFS to explore each possible state of the ring and propagate the minimum distance for each configuration. We can view each state as a node in a graph and use BFS to find the target node with minimum steps.
This solution uses a breadth-first search (BFS) approach to explore each state (current position and current character index in the key string). Each state is added to a queue along with the action step count. For each character in the key, we consider all possible indices in the ring where the character appears and add them to the queue, marking them as visited.
Python
Java
JavaScript
Time Complexity: O(n*m), where n is the length of the key and m is the length of the ring.
Space Complexity: O(n*m) for storing visited states in the queue.
First, we preprocess the positions of each character c in the string ring, and record them in the array pos[c]. Suppose the lengths of the strings key and ring are m and n, respectively.
Then we define f[i][j] as the minimum number of steps to spell the first i+1 characters of the string key, and the j-th character of ring is aligned with the 12:00 direction. Initially, f[i][j]=+infty. The answer is min_{0 leq j < n} f[m - 1][j].
We can first initialize f[0][j], where j is the position where the character key[0] appears in ring. Since the j-th character of ring is aligned with the 12:00 direction, we only need 1 step to spell key[0]. In addition, we need min(j, n - j) steps to rotate ring to the 12:00 direction. Therefore, f[0][j]=min(j, n - j) + 1.
Next, we consider how the state transitions when i geq 1. We can enumerate the position list pos[key[i]] where key[i] appears in ring, and enumerate the position list pos[key[i-1]] where key[i-1] appears in ring, and then update f[i][j], i.e., f[i][j]=min_{k \in pos[key[i-1]]} f[i-1][k] + min(abs(j - k), n - abs(j - k)) + 1.
Finally, we return min_{0 leq j \lt n} f[m - 1][j].
The time complexity is O(m times n^2), and the space complexity is O(m times n). Here, m and n are the lengths of the strings key and ring, respectively.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Dynamic Programming with Memoization | Time Complexity: O(m*n), where m is the length of the `key` and n is the length of the `ring`. |
| Breadth-First Search Approach | Time Complexity: O(n*m), where n is the length of the key and m is the length of the ring. |
| Dynamic Programming | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with Memoization | O(m * n * k) | O(m * n) | Best general solution. Efficient when ring characters repeat and subproblems overlap. |
| Breadth-First Search | O(m * n * k) | O(n) | Useful if you prefer modeling the ring as a graph and computing shortest paths iteratively. |
Freedom Trail - Leetcode 514 - Python • NeetCodeIO • 15,713 views views
Watch 9 more video solutions →Practice Freedom Trail with our built-in code editor and test cases.
Practice on FleetCode