Freedom Trail: Ring DP with Position Tracking

You are given a circular ring with characters on it and a key string you need to spell. At each step, you rotate the ring to align a character at the top, press a button to confirm it, and move on to the next character in the key. Your goal is to find the minimum total number of steps (rotations plus presses) to spell the entire key. This is LeetCode 514: Freedom Trail, a hard DP problem that combines circular distance calculation with position-based state tracking.

The problem

You have a circular ring of characters and a key string you need to spell. At each step, you can rotate the ring clockwise or counterclockwise to align a character at the 12 o'clock position, then press a button to confirm it. Each rotation by one position costs 1 step, and each button press costs 1 step. Find the minimum number of steps (rotations + button presses) to spell the entire key.

For example, with ring = "godding" and key = "gd":

The ring has 7 characters arranged in a circle. The pointer starts at index 0 (the character 'g'). To spell "gd", you need to align 'g' first, then 'd'. Since 'g' is already at the pointer, you just press the button (1 step). Then you rotate clockwise 2 positions to reach 'd' at index 2 and press the button (2 + 1 = 3 steps). Total: 4 steps.

The approach

The key observation is that at each step, you need to decide which occurrence of the next character to rotate to. A character might appear multiple times in the ring, and different choices lead to different total costs. This screams DP.

Define dp[i][j] as the minimum cost to spell key[i:] (from character i onward) when the ring pointer is currently at position j. For each character in the key, you try all positions in the ring where that character appears and take the minimum rotation distance plus the cost of spelling the rest.

The recurrence is:

• For each position j in the ring where ring[j] == key[i]:
  • dp[i][j] = min over all valid previous positions p of (dist(p, j) + 1 + dp[i+1][j])

Where dist(p, j) is the minimum rotation distance between positions p and j on the circular ring.

Step-by-step walkthrough

Let's trace through ring = "godding" and key = "gd" to see how the DP builds the optimal answer.

Notice how having duplicate characters (two 'g' positions and two 'd' positions) forces you to evaluate all options. The greedy choice of "go to the closest one" does not always work across multiple key characters, because a slightly longer rotation now might set you up for a much shorter rotation on the next character. That is exactly why DP is needed here.

The code

def find_rotate_steps(ring, key):
    n = len(ring)
    m = len(key)
    pos = {}
    for i, ch in enumerate(ring):
        pos.setdefault(ch, []).append(i)

    dp = [[float('inf')] * n for _ in range(m + 1)]
    for j in range(n):
        dp[m][j] = 0

    for i in range(m - 1, -1, -1):
        for j in range(n):
            for k in pos[key[i]]:
                dist = min(abs(j - k), n - abs(j - k))
                dp[i][j] = min(dp[i][j], dist + 1 + dp[i + 1][k])

    return dp[0][0]

Here is what each part does:

• pos dictionary: maps each character to the list of indices where it appears in the ring. This avoids scanning the ring repeatedly.
• dp[m][j] = 0: base case. Once you have spelled all characters in the key, no more cost is needed regardless of the pointer position.
• Triple nested loop: for each key character i (from back to front), for each possible pointer position j, try every ring position k where key[i] appears. Compute the rotation distance, add 1 for the button press, and add the future cost dp[i+1][k].
• dp[0][0]: the answer. Minimum cost to spell the entire key starting from position 0.

We fill the table from the last key character backward. This way, when we compute dp[i][j], the values dp[i+1][k] are already available.

Complexity analysis

Where m = len(key) and n = len(ring).

Time: For each of the m key characters, we iterate over all n ring positions, and for each one we check up to n candidate positions where the target character appears. In the worst case (all ring characters are the same), the inner loop runs n times, giving O(m * n^2). In practice, it is much faster because each character typically appears only a few times.

Space: The DP table has m + 1 rows and n columns. You could optimize to O(n) by only keeping two rows at a time, since each row only depends on the next row.

Building blocks

This problem is built on two core ideas:

1. Circular distance calculation: given two positions on a ring of length n, the minimum distance is min(abs(i - j), n - abs(i - j)). This shows up in any problem involving circular arrays or rotations. Recognizing this pattern saves you from off-by-one errors and lets you handle the wrap-around cleanly.

2. DP with state = (key index, ring position): the state tracks where you are in the key and where the pointer currently sits on the ring. This two-dimensional state is common in problems where your current configuration affects future costs. You have seen similar ideas in problems like Edit Distance, where the state is (i, j) representing positions in two strings.

Edge cases

1. Key character appears only once in the ring: no choice to make for that character. You must rotate to that single position. The DP still handles this correctly since the inner loop has only one candidate.

2. Ring has all identical characters: every position is valid for every key character. The optimal strategy is to stay at the current position (0 rotations + 1 press per character). The DP correctly computes this because the minimum distance from any position to itself is 0.

3. Key is a single character: only one step of DP. You just find the closest occurrence of that character from position 0 and add 1 for the button press.

4. Ring length is 1: the ring has a single character, which must equal every character in the key. Total cost is len(key) (one press per character, zero rotations).

From understanding to recall

You now understand how to set up the DP table, compute circular distances, and handle duplicate characters in the ring. But this problem has a few moving parts that are easy to mix up under pressure: the circular distance formula, the direction of the DP fill (backward through the key), and remembering that each key character might appear at multiple ring positions. These details matter, and they tend to slip away if you do not practice writing the solution from scratch.

The position-tracking DP pattern shows up in other problems too, any time your current location in one structure affects the cost of future moves in another. Drilling Freedom Trail with spaced repetition locks in this pattern so you can recognize it instantly and write the solution without hesitation.

Related posts

• Edit Distance - Another DP problem that minimizes cost of transformations
• Coin Change - DP optimization problem finding minimum cost to reach a target
• Word Break - DP problem where you track position in a string and choose from multiple options at each step