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

| Operation | Cost |
|---|---:|
| Rotate the ring one position clockwise | `1` |
| Rotate the ring one position counterclockwise | `1` |
| Press the center button to select the current character | `1` |

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

| Item | Meaning |
|---|---|
| Input | Strings `ring` and `key` |
| Output | Minimum number of steps |
| Rotation | Clockwise or counterclockwise |
| Pressing | Costs `1` step per key character |

Function shape:

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

## Examples

Example 1:

```python
ring = "godding"
key = "gd"
```

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

```text
g
```

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

Cost so far:

```text
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:

```text
2
```

Then we press the button.

Cost for this character:

```text
2 + 1 = 3
```

Total:

```text
1 + 3 = 4
```

So the answer is:

```python
4
```

## First Thought: Try Every Matching Character

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

For example:

```python
ring = "godding"
```

The character `"g"` appears at indices:

```text
0, 6
```

The character `"d"` appears at indices:

```text
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:

| State part | Meaning |
|---|---|
| Current ring position | Which ring index is at `12:00` |
| Current key index | Which character of `key` we need next |

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:

```text
ring[pos] is currently at 12:00
```

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

```text
abs(pos - next_pos)
```

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

```text
n - abs(pos - next_pos)
```

So the minimum rotation cost is:

```text
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:

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

Define:

```python
dfs(pos, i)
```

as the minimum number of steps needed to spell:

```text
key[i:]
```

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

For each possible `next_pos` where:

```python
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:

```python
if i == len(key):
    return 0
```

The initial state is:

```python
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:

| Symbol | Meaning |
|---|---|
| `n` | Length of `ring` |
| `m` | Length of `key` |

There are at most `n * m` states.

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

| Metric | Value | Why |
|---|---|---|
| Time | `O(m * n^2)` | Up to `m * n` states, each trying up to `n` positions |
| Space | `O(m * n)` | Memoization table |

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

## Implementation

```python
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:

```python
n = len(ring)
```

Then build a character-to-positions map:

```python
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:

```python
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:

```python
if key_index == len(key):
    return 0
```

For the current target character:

```python
target = key[key_index]
```

try every ring position containing it:

```python
for next_pos in positions[target]:
```

Compute the direct distance:

```python
distance = abs(pos - next_pos)
```

Then compute the shorter circular rotation:

```python
rotate_steps = min(distance, n - distance)
```

The total cost for this choice is:

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

The `+ 1` is the button press.

Finally, return the best possible value.

## Testing

```python
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:

| Test | Why |
|---|---|
| `"godding"`, `"gd"` | Standard sample |
| Full word from same ring | Checks repeated decisions |
| `"abcde"`, `"ade"` | Uses both clockwise and counterclockwise movement |
| Repeated same character | Pressing dominates rotation |
| Larger case | Checks memoization and repeated characters |