Skip to main content
Talentd

Freedom Trail - Solution & Explanation

HardStringDynamic ProgrammingDepth-First SearchBreadth-First Search20 min readAsked at: Uber, Google, PhonePe
Practice this problem

Problem Statement

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]:

  1. You can rotate the ring clockwise or anticlockwise by one place, which counts as one step. The final purpose of the rotation is to align one of ring's characters at the "12:00" direction, where this character must equal key[i].
  2. If the character 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 <= 100
  • ring and key consist of only lower case English letters.
  • It is guaranteed that key could always be spelled by rotating ring.

Approach Overview

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 1: Dynamic Programming with Memoization

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.

Code

PythonJavaC++

Python

Java

C++

Complexity

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.

Try this approach in the editor →

Approach 2: Breadth-First Search Approach

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.

Code

PythonJavaJavaScript

Python

Java

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: Dynamic Programming

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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`.
Space Complexity: O(m*n) for the memoization table and index dictionary.

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.
Space Complexity: O(n*m) for storing visited states in the queue.

Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dynamic Programming with MemoizationO(m * n * k)O(m * n)Best general solution. Efficient when ring characters repeat and subproblems overlap.
Breadth-First SearchO(m * n * k)O(n)Useful if you prefer modeling the ring as a graph and computing shortest paths iteratively.

Video Solution

Freedom Trail - Leetcode 514 - Python • NeetCodeIO • 15,907 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Freedom Trail easy or hard?
Freedom Trail is classified as a Hard problem because it combines circular distance calculation, dynamic programming state design, and multiple candidate transitions for each step. Efficient solutions require recognizing overlapping subproblems and minimizing rotation costs.
Freedom Trail Python/Java solution
Both Python and Java implementations use the same core idea: preprocess the ring to map characters to indices, then compute the minimal rotation cost using DP with memoization or BFS. Python often uses dictionaries and recursion with caching, while Java implementations use arrays or hash maps with memo tables.
How to solve Freedom Trail in O(n)?
A strict O(n) solution is not feasible because every character in the key may appear at multiple positions in the ring. The optimal strategy evaluates candidate ring indices for each key character using dynamic programming or BFS. The practical complexity becomes O(m * n * k) after preprocessing character positions.
What is the best approach for Freedom Trail?
Dynamic Programming with memoization is the most common and interview-preferred solution. The state is defined by the current ring pointer position and the index in the key. By caching results for (keyIndex, ringPosition), the algorithm avoids recomputation and efficiently finds the minimal rotation cost. The overall complexity is roughly O(m * n * k).
Is Freedom Trail asked at Google/Amazon/Meta?
Freedom Trail is a classic hard-level dynamic programming problem involving circular strings and state transitions. Variants of this problem appear in interviews at large tech companies such as Google, Amazon, and Meta when evaluating DP and shortest-path reasoning.
What data structure is used in Freedom Trail?
The solution typically uses hash maps (or dictionaries) to store indices of each character in the ring, along with dynamic programming tables or memoization caches. Some implementations also use queues for BFS when modeling the ring as a graph traversal problem.
What is the time complexity of Freedom Trail?
The typical optimized solution runs in O(m * n * k) time, where m is the length of the key, n is the ring length, and k is the average number of occurrences of a character in the ring. Space complexity is O(m * n) for memoization in the dynamic programming approach.

Ready to solve this problem?

Practice Freedom Trail with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Substring Without Repeating Characters

Next

Longest Palindromic Substring