Watch 10 video solutions for Freedom Trail, a hard level problem involving String, Dynamic Programming, Depth-First Search. This walkthrough by NeetCodeIO has 15,713 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |