What is the freedom trail problem in Python?

We’re provided a string ring representing the code in our ring and another string key signifying the keyword that needs to be spelled. Our task is to find the minimum number of operations to spell out the target string.

An example of a freedom trail problem
An example of a freedom trail problem

To begin, the first character of the ring is positioned at the 12:00 position. We need to spell each separate character in key. For this, we’ll have to rotate the ring clockwise or counterclockwise, aligning each key character at the 12:00 position before counting the character.

Note: After aligning, confirming that character will also count as an additional step. In the diagram above, confirming A counts as one step. Moving B to 12:00 counts as another step, and confirming it also counts as a third step. Hence, the minimum steps are three.

Code

In our solution, we’ll be using a helper function to help calculate the minimum steps required to spell key. It uses memoization to store previous results and avoid redundant calculations. It iterates through ring and calculates the optimal rotations to return the minimum steps needed to complete the task.

The code for this solution is provided below:

def freedomtrail(ring, key):
  return fthelper(0, 0) + len(key)
def fthelper(i, j):
  memo = {}
  if j == len(key):
    return 0
  if (i, j) in memo:
    return memo[(i, j)]
  char = key[j]
  minsteps = float('inf')
  for k in range(len(ring)):
    if ring[k] == char:
      rotate = abs(k - i)
      minsteps = min(minsteps, rotate + fthelper(k, j + 1))
  memo[(i, j)] = minsteps
  return minsteps
ring = "right"
key = "rh"
result = freedomtrail(ring, key)
print("The minimum operations are: " + str(result))

The explanation of this code is given below:

  • Line 1: We define our freedomtrail function, which takes ring and key as parameters. It calculates the minimum steps needed to spell out key starting from index 0 of ring.

  • Line 2: We call the fthelper function with parameters (0, 0). We then add the length of key to the result.

  • Line 4: We define the fthelper function, which takes the indexes i and j as parameters.

  • Line 5: We define an empty dictionary memo to store our steps.

  • Lines 6–7: This is the base case check for when j reaches the length of key. This will indicate that we’ve spelled the word.

  • Lines 9–10: We check whether we’ve traversed this path in the dictionary.

  • Line 12: We extract the character we need to search in the ring.

  • Line 13: We set minsteps to positive infinity to store the actual minimum number of steps later on.

  • Line 15: We loop through the entire ring.

  • Lines 16–18: Each time the character is found at index k, we calculate the steps required to rotate the ring from index i to k. We recursively call fthelper with the new position k along with j + 1 to match the next character we need in key. We then update the minimum steps required among all possible rotations in the ring.

  • Lines 20–21: We update and store the minimum steps required for the indexes in memo to avoid recalculations. We then return minsteps.

  • Lines 23–26: This is the code to run our functions.

To try other examples, you can change the inputs in the code above.

Free AI Mock Interviews
Coding Interview
Coding PatternsFree Interview
Gain insights and practical experience with coding patterns through targeted MCQs and coding problems, designed to match and challenge your expertise level.
System Design
YouTubeFree Interview
Learn to design a video streaming platform like YouTube by tackling functional and non-functional requirements, core components, and high-level to detailed design challenges.

Free Resources

Copyright ©2025 Educative, Inc. All rights reserved