LeetCode 514: Freedom Trail

Problem Restatement

We are given a circular ring represented by a string ring.

We are also given a string key.

The ring starts with ring[0] aligned at the 12:00 position.

To spell each character in key, we may:

For each character in key, we must rotate the ring until some matching character is at 12:00, then press the button.

Return the minimum total number of steps needed to spell the whole key.

The official problem describes this circular dial and asks for the minimum number of rotate and press operations needed to spell key.

Input and Output

Function shape:

class Solution:
    def findRotateSteps(self, ring: str, key: str) -> int:
        ...

Examples

Example 1:

ring = "godding"
key = "gd"

At the start, the character at 12:00 is:

g

The first key character is also "g", so we only press the button.

Cost so far:

1

The next key character is "d".

In ring = "godding", the character "d" appears at indices 2 and 3.

From index 0, the closest "d" is at index 2.

The circular distance is:

2

Then we press the button.

Cost for this character:

2 + 1 = 3

Total:

1 + 3 = 4

So the answer is:

4

First Thought: Try Every Matching Character

When we need to spell a character, it may appear multiple times in the ring.

For example:

ring = "godding"

The character "g" appears at indices:

0, 6

The character "d" appears at indices:

2, 3

Choosing one occurrence may make the current step cheap but make the next step expensive.

So we cannot always choose the closest current occurrence greedily.

We need to compare future costs too.

Problem With Plain Backtracking

A plain recursive search tries every possible occurrence for each key character.

If many characters repeat, the number of possible paths grows quickly.

The same state can be reached many times.

A state is determined by:

If we already know the minimum cost from a state, we should reuse it.

That leads to dynamic programming with memoization.

Key Insight

The ring does not need to be physically rotated.

Instead, keep an integer pos.

pos means:

ring[pos] is currently at 12:00

To move from position pos to position next_pos, the circular distance is:

abs(pos - next_pos)

But because the ring is circular, we can also move the other way around:

n - abs(pos - next_pos)

So the minimum rotation cost is:

min(abs(pos - next_pos), n - abs(pos - next_pos))

For each needed key character, we try all ring positions containing that character.

Algorithm

Build a map from character to all positions where it appears in ring.

Example:

positions = {
    "g": [0, 6],
    "o": [1],
    "d": [2, 3],
    "i": [4],
    "n": [5],
}

Define:

dfs(pos, i)

as the minimum number of steps needed to spell:

key[i:]

when ring[pos] is currently at 12:00.

For each possible next_pos where:

ring[next_pos] == key[i]

compute:

1. Rotation cost from pos to next_pos
2. Press cost 1
3. Remaining cost dfs(next_pos, i + 1)

Take the minimum.

Base case:

if i == len(key):
    return 0

The initial state is:

dfs(0, 0)

because ring[0] starts at 12:00.

Correctness

For any state dfs(pos, i), the ring position and the next key index fully determine the remaining problem.

To spell key[i], the algorithm considers every ring index next_pos containing that character. These are exactly all valid choices for the next button press.

For each choice, the algorithm adds the minimum circular rotation distance from pos to next_pos, plus one step for pressing the button, plus the optimal cost of spelling the remaining suffix key[i + 1:].

Taking the minimum over all valid next_pos gives the optimal cost for that state.

The base case returns 0 after all key characters have been spelled.

By memoizing states, the algorithm computes each distinct state once, while preserving the same optimal recurrence.

Therefore dfs(0, 0) returns the minimum total number of steps needed to spell the whole key.

Complexity

Let:

There are at most n * m states.

For each state, we may try up to n matching positions in the worst case.

In practice, it is often faster because each character usually appears in fewer than n positions.

Implementation

from typing import List
from collections import defaultdict
from functools import lru_cache

class Solution:
    def findRotateSteps(self, ring: str, key: str) -> int:
        n = len(ring)

        positions = defaultdict(list)

        for i, ch in enumerate(ring):
            positions[ch].append(i)

        @lru_cache(None)
        def dfs(pos: int, key_index: int) -> int:
            if key_index == len(key):
                return 0

            target = key[key_index]
            best = float("inf")

            for next_pos in positions[target]:
                distance = abs(pos - next_pos)
                rotate_steps = min(distance, n - distance)

                total_steps = (
                    rotate_steps
                    + 1
                    + dfs(next_pos, key_index + 1)
                )

                best = min(best, total_steps)

            return best

        return dfs(0, 0)

Code Explanation

First, store the ring length:

n = len(ring)

Then build a character-to-positions map:

positions = defaultdict(list)

for i, ch in enumerate(ring):
    positions[ch].append(i)

This lets us quickly find all valid positions for each key character.

The memoized DFS state is:

dfs(pos, key_index)

pos is the current ring index at 12:00.

key_index is the next character we need to spell.

If all key characters have been spelled:

if key_index == len(key):
    return 0

For the current target character:

target = key[key_index]

try every ring position containing it:

for next_pos in positions[target]:

Compute the direct distance:

distance = abs(pos - next_pos)

Then compute the shorter circular rotation:

rotate_steps = min(distance, n - distance)

The total cost for this choice is:

rotate_steps + 1 + dfs(next_pos, key_index + 1)

The + 1 is the button press.

Finally, return the best possible value.

Testing

def test_find_rotate_steps():
    s = Solution()

    assert s.findRotateSteps("godding", "gd") == 4
    assert s.findRotateSteps("godding", "godding") == 13
    assert s.findRotateSteps("abcde", "ade") == 6
    assert s.findRotateSteps("aaa", "aaaa") == 4
    assert s.findRotateSteps("caotmcaataijjxi", "oatjiioicitatajtijciocjcaaxaaatmctxamacaamjjx") == 137

    print("all tests passed")

Test meaning: