Freedom Trail

Hard

#0499Time: 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.

Patterns

Dynamic Programming

Algorithms

Depth-First Search Breadth-First Search

Data structures

String

Prompt

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

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].
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:

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

4 approaches with complexity analysis and trade-offs.

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.

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).

Walkthrough

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.

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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.

1class Solution {2    private int[][] memo;3    private String ring;4    private String key;5    private int ringLen;6 7    public int findRotateSteps(String ring, String key) {8        this.ring = ring;9        this.key = key;10        this.ringLen = ring.length();11        this.memo = new int[key.length()][ringLen];12        for (int[] row : memo) {13            Arrays.fill(row, -1);14        }15        return solve(0, 0);16    }17 18    private int solve(int keyIndex, int ringIndex) {19        if (keyIndex == key.length()) {20            return 0;21        }22        if (memo[keyIndex][ringIndex] != -1) {23            return memo[keyIndex][ringIndex];24        }25 26        int minSteps = Integer.MAX_VALUE;27        char targetChar = key.charAt(keyIndex);28 29        for (int i = 0; i < ringLen; i++) {30            if (ring.charAt(i) == targetChar) {31                int dist = Math.abs(ringIndex - i);32                int rotateSteps = Math.min(dist, ringLen - dist);33                int totalSteps = rotateSteps + 1 + solve(keyIndex + 1, i);34                minSteps = Math.min(minSteps, totalSteps);35            }36        }37        38        memo[keyIndex][ringIndex] = minSteps;39        return minSteps;40    }41}

Complexity

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).

Trade-offs

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.

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.

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].

Walkthrough

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.

1class Solution {2    public int findRotateSteps(String ring, String key) {3        int ringLen = ring.length();4        int keyLen = key.length();5        int[][] dp = new int[keyLen + 1][ringLen];6 7        for (int i = keyLen - 1; i >= 0; i--) {8            for (int j = 0; j < ringLen; j++) {9                dp[i][j] = Integer.MAX_VALUE;10                char targetChar = key.charAt(i);11                for (int k = 0; k < ringLen; k++) {12                    if (ring.charAt(k) == targetChar) {13                        int dist = Math.abs(j - k);14                        int rotateSteps = Math.min(dist, ringLen - dist);15                        int totalSteps = rotateSteps + 1 + dp[i + 1][k];16                        dp[i][j] = Math.min(dp[i][j], totalSteps);17                    }18                }19            }20        }21        return dp[0][0];22    }23}

Complexity

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.

Trade-offs

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.

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).

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.

Walkthrough

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.

1class Solution {2    public int findRotateSteps(String ring, String key) {3        int ringLen = ring.length();4        int keyLen = key.length();5        6        int[] dp = new int[ringLen];7 8        for (int i = keyLen - 1; i >= 0; i--) {9            int[] next_dp = new int[ringLen];10            Arrays.fill(next_dp, Integer.MAX_VALUE);11            char targetChar = key.charAt(i);12            13            for (int j = 0; j < ringLen; j++) { // For each starting position j for key[i]14                for (int k = 0; k < ringLen; k++) { // For each possible destination k for key[i]15                    if (ring.charAt(k) == targetChar) {16                        int dist = Math.abs(j - k);17                        int rotateSteps = Math.min(dist, ringLen - dist);18                        int totalSteps = rotateSteps + 1 + dp[k];19                        next_dp[j] = Math.min(next_dp[j], totalSteps);20                    }21                }22            }23            dp = next_dp;24        }25        26        return dp[0];27    }28}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class 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 ; } }

1class 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 ; } };

1class 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 ]])

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class 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 ; } }

1class 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 ; } };

1class 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 ]])

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.