# Freedom Trail
**Difficulty:** HARD
[External](https://leetcode.com/problems/freedom-trail)
Canonical: https://scaleengineer.com/dsa/problems/freedom-trail
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** String
---
## Problem
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:**

![](https://assets.glich.co/dsa/freedom-trail/image0.jpg) 

**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`.

# Approaches
## Brute-Force Recursion
This approach directly translates the problem into a recursive structure. It explores every possible sequence of rotations to spell the `key`. For each character in the `key`, it tries rotating to every occurrence of that character on the `ring` and recursively calculates the cost for the rest of the `key`. This exhaustive search guarantees finding the minimum steps but at an exponential time cost.
**Time:** O(R^K), where R is the length of the `ring` and K is the length of the `key`. At each of the K steps (one for each character in `key`), we might branch up to R times (for each character in `ring`). This exponential complexity makes it infeasible. · **Space:** O(K), where K is the length of the `key`. This space is used by the recursion call stack.
**Pros:** Simple to understand and implement as it directly models the problem's decision-making process.
**Cons:** Extremely inefficient due to the massive number of redundant computations for the same subproblems.; Will result in a 'Time Limit Exceeded' (TLE) error for all but the smallest inputs.
### Explanation
The core idea is to define a function, say `solve(keyIndex, ringIndex)`, which calculates the minimum steps to spell the suffix of the key starting from `keyIndex`, given that the character `ring[ringIndex]` is currently at the 12 o'clock position. The base case for the recursion is when we have successfully spelled all characters (`keyIndex == key.length()`), where the cost is 0. In the recursive step, to spell `key[keyIndex]`, we find all its occurrences in the `ring`. For each occurrence, we calculate the cost to rotate to it, add 1 for the button press, and add the result of the recursive call for the next character (`keyIndex + 1`) from this new ring position. We then take the minimum cost among all these choices. This method is a classic brute-force search that explores the entire decision tree.
### Algorithm
- Define a recursive function `findMinSteps(keyIndex, ringIndex)` that computes the minimum steps to spell `key` from `keyIndex` onwards, given `ring[ringIndex]` is at the 12 o'clock position.
- **Base Case:** If `keyIndex` equals the length of `key`, all characters have been spelled, so return 0.
- **Recursive Step:** For the character `key[keyIndex]`, iterate through the `ring` to find all its occurrences.
- For each occurrence at index `i`:
  - Calculate the shortest rotational distance between the current `ringIndex` and the new index `i`. The distance is `min(abs(ringIndex - i), ring.length() - abs(ringIndex - i))`.
  - The total steps for this choice is `rotational_distance + 1 (for the press) + findMinSteps(keyIndex + 1, i)`.
- The function returns the minimum of these total steps over all occurrences of `key[keyIndex]`.
- The initial call to start the process is `findMinSteps(0, 0)`.

## Top-Down Dynamic Programming (Memoization)
This approach enhances the brute-force recursion by adding memoization, a technique also known as top-down dynamic programming. We notice that the recursive solution repeatedly calculates the minimum steps for the same state (`keyIndex`, `ringIndex`). By storing the result of each subproblem in a cache (a 2D array) the first time it's computed, we can avoid redundant calculations and retrieve the stored result in constant time for subsequent calls with the same state.
**Time:** O(K * R^2). There are `K * R` states, and for each state, we may iterate through the entire `ring` of length R to find the next character. · **Space:** O(K * R), where K is `key.length()` and R is `ring.length()`. This is for the memoization table. The recursion stack adds O(K).
**Pros:** Drastically improves time complexity compared to brute force, making it a viable solution.; Guaranteed to find the optimal solution.; Often more intuitive to write than the bottom-up iterative version.
**Cons:** Requires O(K * R) space for the memoization table, which might be large for maximum constraints.; May be slightly slower than an iterative bottom-up DP approach due to recursion overhead.
### Explanation
We define a recursive function `solve(keyIndex, ringIndex)` and a 2D memoization table `memo`. When the function is called, it first checks if the result for the state `(keyIndex, ringIndex)` is already stored in `memo`. If it is, the stored value is returned. Otherwise, it computes the result by exploring all possible next moves, just like the brute-force method. The key difference is that once the minimum steps for a state are calculated, they are stored in `memo[keyIndex][ringIndex]`. This ensures that each of the `key.length() * ring.length()` subproblems is solved only once, drastically reducing the time complexity from exponential to polynomial.

```java
class Solution {
    private int[][] memo;
    private String ring;
    private String key;
    private int ringLen;

    public int findRotateSteps(String ring, String key) {
        this.ring = ring;
        this.key = key;
        this.ringLen = ring.length();
        this.memo = new int[key.length()][ringLen];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }
        return solve(0, 0);
    }

    private int solve(int keyIndex, int ringIndex) {
        if (keyIndex == key.length()) {
            return 0;
        }
        if (memo[keyIndex][ringIndex] != -1) {
            return memo[keyIndex][ringIndex];
        }

        int minSteps = Integer.MAX_VALUE;
        char targetChar = key.charAt(keyIndex);

        for (int i = 0; i < ringLen; i++) {
            if (ring.charAt(i) == targetChar) {
                int dist = Math.abs(ringIndex - i);
                int rotateSteps = Math.min(dist, ringLen - dist);
                int totalSteps = rotateSteps + 1 + solve(keyIndex + 1, i);
                minSteps = Math.min(minSteps, totalSteps);
            }
        }
        
        memo[keyIndex][ringIndex] = minSteps;
        return minSteps;
    }
}
```
### Algorithm
- The recursive structure is the same as the brute-force approach.
- A 2D array, `memo[key.length()][ring.length()]`, is used to store the results of subproblems. It's initialized with a sentinel value (e.g., -1).
- Before computing `solve(keyIndex, ringIndex)`, check if `memo[keyIndex][ringIndex]` already has a valid result. If so, return it immediately.
- If the result is not in the memo table, compute it as in the brute-force approach.
- After computing the result, store it in `memo[keyIndex][ringIndex]` before returning.
- To optimize finding character locations, pre-process the `ring` to store indices of each character in a hash map.

## Bottom-Up Dynamic Programming
This approach uses bottom-up dynamic programming, which is an iterative alternative to top-down memoization. We build the solution from the smallest subproblems up to the main problem. We use a 2D table, `dp[i][j]`, to store the minimum steps to spell the suffix of the key starting at index `i`, given the ring is at position `j`. We fill this table starting from the end of the key.
**Time:** O(K * R^2). We have three nested loops: iterating through the key, the current ring positions, and the next ring positions. · **Space:** O(K * R) for the 2D DP table.
**Pros:** Avoids recursion overhead, which can lead to a slight performance improvement over the memoized approach.; Systematic and tabular, which can be easier to debug for some.
**Cons:** Uses O(K * R) space, which is not optimal.
### Explanation
We iterate through the key characters in reverse. For each character `key[i]`, we compute the costs for all possible starting ring positions `j`. The cost `dp[i][j]` is determined by looking at the costs already computed for the next character, `key[i+1]`, which are stored in `dp[i+1]`. Specifically, to find `dp[i][j]`, we consider rotating to each occurrence `k` of `key[i]` in the ring. The cost for choosing `k` is the rotation steps from `j` to `k`, plus one for the press, plus the pre-calculated minimum cost to continue from that point, `dp[i+1][k]`. We take the minimum over all possible `k`. The process starts with the base case where `i = key.length()`, for which the cost is zero. The final answer is `dp[0][0]`, the cost to spell the whole key starting at ring position 0.

```java
class Solution {
    public int findRotateSteps(String ring, String key) {
        int ringLen = ring.length();
        int keyLen = key.length();
        int[][] dp = new int[keyLen + 1][ringLen];

        for (int i = keyLen - 1; i >= 0; i--) {
            for (int j = 0; j < ringLen; j++) {
                dp[i][j] = Integer.MAX_VALUE;
                char targetChar = key.charAt(i);
                for (int k = 0; k < ringLen; k++) {
                    if (ring.charAt(k) == targetChar) {
                        int dist = Math.abs(j - k);
                        int rotateSteps = Math.min(dist, ringLen - dist);
                        int totalSteps = rotateSteps + 1 + dp[i + 1][k];
                        dp[i][j] = Math.min(dp[i][j], totalSteps);
                    }
                }
            }
        }
        return dp[0][0];
    }
}
```
### Algorithm
- Create a 2D DP table `dp[key.length() + 1][ring.length()]`.
- `dp[i][j]` will store the minimum steps to spell the suffix `key[i:]` starting with `ring[j]` at 12 o'clock.
- **Base Case:** Initialize the last row, `dp[key.length()][j] = 0` for all `j`, as no steps are needed for an empty key suffix.
- Iterate backwards from `i = key.length() - 1` down to `0`.
- For each `i`, iterate through all possible current ring positions `j` from `0` to `ring.length() - 1`.
- For each `j`, find all occurrences `k` of `key.charAt(i)` in the `ring`.
- The transition is `dp[i][j] = min(dp[i][j], rotation_steps(j, k) + 1 + dp[i+1][k])`.
- The final answer is `dp[0][0]`.

## Space-Optimized Bottom-Up Dynamic Programming
This is the most efficient approach, optimizing the space complexity of the bottom-up DP. By observing that the calculation for the current key character `i` only requires the results from the immediately following character `i+1`, we can discard older results. Instead of a full 2D DP table, we only need to maintain two rows: one for the previous state (for `i+1`) and one for the current state we are computing (for `i`). This reduces the space complexity from O(K * R) to O(R).
**Time:** O(K * R^2). The time complexity is not improved over the standard DP, but it's the best known for this problem. · **Space:** O(R), where R is the length of the `ring`. We only need two arrays of size R to store the DP states for the current and previous steps.
**Pros:** Optimal space complexity of O(R).; Maintains the optimal time complexity of O(K * R^2).
**Cons:** The logic can be slightly more complex to manage with array swapping or copying compared to the straightforward 2D DP table.
### Explanation
We start with a 1D array, `dp`, of size `ring.length()`, initialized to all zeros. This array represents the costs for the state *after* the entire key has been spelled. We then loop backwards through the key. In each iteration `i`, we create a new array, `next_dp`, to store the costs for spelling `key[i:]`. For each starting ring position `j`, we calculate `next_dp[j]` by considering all possible moves to an occurrence `k` of `key.charAt(i)`. The cost is `rotation_steps(j, k) + 1 + dp[k]`, where `dp[k]` holds the optimal cost from the previous step (`i+1`). After computing all values for `next_dp`, we replace the old `dp` array with `next_dp` and proceed to the next character `i-1`. The final answer is the cost stored at index 0 of the `dp` array after the loop completes.

```java
class Solution {
    public int findRotateSteps(String ring, String key) {
        int ringLen = ring.length();
        int keyLen = key.length();
        
        int[] dp = new int[ringLen];

        for (int i = keyLen - 1; i >= 0; i--) {
            int[] next_dp = new int[ringLen];
            Arrays.fill(next_dp, Integer.MAX_VALUE);
            char targetChar = key.charAt(i);
            
            for (int j = 0; j < ringLen; j++) { // For each starting position j for key[i]
                for (int k = 0; k < ringLen; k++) { // For each possible destination k for key[i]
                    if (ring.charAt(k) == targetChar) {
                        int dist = Math.abs(j - k);
                        int rotateSteps = Math.min(dist, ringLen - dist);
                        int totalSteps = rotateSteps + 1 + dp[k];
                        next_dp[j] = Math.min(next_dp[j], totalSteps);
                    }
                }
            }
            dp = next_dp;
        }
        
        return dp[0];
    }
}
```
### Algorithm
- Observe that `dp[i]` only depends on `dp[i+1]`.
- Use two 1D arrays, `dp` and `prev_dp`, each of size `ring.length()`.
- Initialize `prev_dp` with zeros. This represents the costs after the last character of the key is spelled.
- Iterate `i` from `key.length() - 1` down to `0`.
- In each iteration, compute a new `dp` array based on `prev_dp`.
- `dp[j]` is calculated by finding the minimum of `rotation_steps(j, k) + 1 + prev_dp[k]` over all occurrences `k` of `key.charAt(i)`.
- After the inner loops complete for a given `i`, set `prev_dp = dp` for the next iteration.
- The final answer is `prev_dp[0]` after the main loop finishes.

# Solutions
### Java

```java
class Solution { public int findRotateSteps ( String ring , String key ) { int m = key . length (), n = ring . length (); List < Integer >[] pos = new List [ 26 ]; Arrays . setAll ( pos , k -> new ArrayList <>()); for ( int i = 0 ; i < n ; ++ i ) { int j = ring . charAt ( i ) - 'a' ; pos [ j ]. add ( i ); } int [][] f = new int [ m ][ n ]; for ( var g : f ) { Arrays . fill ( g , 1 << 30 ); } for ( int j : pos [ key . charAt ( 0 ) - 'a' ]) { f [ 0 ][ j ] = Math . min ( j , n - j ) + 1 ; } for ( int i = 1 ; i < m ; ++ i ) { for ( int j : pos [ key . charAt ( i ) - 'a' ]) { for ( int k : pos [ key . charAt ( i - 1 ) - 'a' ]) { f [ i ][ j ] = Math . min ( f [ i ][ j ], f [ i - 1 ][ k ] + Math . min ( Math . abs ( j - k ), n - Math . abs ( j - k )) + 1 ); } } } int ans = 1 << 30 ; for ( int j : pos [ key . charAt ( m - 1 ) - 'a' ]) { ans = Math . min ( ans , f [ m - 1 ][ j ]); } return ans ; } }
```

### CPP

```cpp
class Solution { public: int findRotateSteps ( string ring , string key ) { int m = key . size (), n = ring . size (); vector < int > pos [ 26 ]; for ( int j = 0 ; j < n ; ++ j ) { pos [ ring [ j ] - 'a' ]. push_back ( j ); } int f [ m ][ n ]; memset ( f , 0x3f , sizeof ( f )); for ( int j : pos [ key [ 0 ] - 'a' ]) { f [ 0 ][ j ] = min ( j , n - j ) + 1 ; } for ( int i = 1 ; i < m ; ++ i ) { for ( int j : pos [ key [ i ] - 'a' ]) { for ( int k : pos [ key [ i - 1 ] - 'a' ]) { f [ i ][ j ] = min ( f [ i ][ j ], f [ i - 1 ][ k ] + min ( abs ( j - k ), n - abs ( j - k )) + 1 ); } } } int ans = 1 << 30 ; for ( int j : pos [ key [ m - 1 ] - 'a' ]) { ans = min ( ans , f [ m - 1 ][ j ]); } return ans ; } };
```

### Python

```python
class Solution : def findRotateSteps ( self , ring : str , key : str ) -> int : m , n = len ( key ), len ( ring ) pos = defaultdict ( list ) for i , c in enumerate ( ring ): pos [ c ]. append ( i ) f = [[ inf ] * n for _ in range ( m )] for j in pos [ key [ 0 ]]: f [ 0 ][ j ] = min ( j , n - j ) + 1 for i in range ( 1 , m ): for j in pos [ key [ i ]]: for k in pos [ key [ i - 1 ]]: f [ i ][ j ] = min ( f [ i ][ j ], f [ i - 1 ][ k ] + min ( abs ( j - k ), n - abs ( j - k )) + 1 ) return min ( f [ - 1 ][ j ] for j in pos [ key [ - 1 ]])
```