514. Freedom Trail - Explanation
Description
The characters of ring sit around a circular dial. Initially, ring[0] is at the selection position. Rotating the dial by one character in either direction costs one step. Pressing the selection button costs one more step and appends the selected character. Spell key in order and return the minimum total steps, including button presses. The dial keeps its position between presses, and every character in key appears in ring.
Example 1:
Input: ring = "abcde"
key = "ea"
Output: 4Explanation: Rotate one position from a to e and press, then rotate one position back to a and press again. Two rotations and two presses cost 4 steps.
Example 2:
Input: ring = "abca"
key = "aa"
Output: 2Explanation: The dial starts on a. Press twice without rotating to spell aa in 2 steps.
Example 3:
Input: ring = "ab"
key = "bbb"
Output: 4Explanation: Rotate once from a to b, then press three times. The total is 1 + 3 = 4 steps.
Constraints:
1 <= ring.length, key.length <= 100- Both strings contain only lowercase English letters.
- Every letter in
keyoccurs inring.
Topics
Prerequisites
Before attempting this problem, you should be comfortable with:
- Dynamic Programming - Breaking down problems into overlapping subproblems with optimal substructure
- Memoization - Caching recursive results to avoid redundant computation
- Circular Array Distance - Calculating minimum distance in a wrap-around structure
- State Space Analysis - Identifying the parameters that define unique subproblems (position, index)
- Bottom-Up DP Conversion - Translating recursive solutions into iterative table-filling approaches
1. Recursion
Intuition
Imagine a circular dial with letters. To spell a word, we rotate the dial to align each required letter with the top position, then press a button. The challenge is finding the minimum total rotations.
For each character in the key, we might have multiple positions on the ring that match. From our current position, we can rotate clockwise or counterclockwise to reach any matching position. We try all possibilities recursively and take the minimum.
Since the ring is circular, the distance between two positions is the minimum of going directly or wrapping around.
Algorithm
- Define a recursive function
dfs(r, k)whereris the current ring position andkis the current index in the key. - Base case: if
kequals the key length, return0. - For each position
iin the ring wherering[i]matcheskey[k]:- Calculate the minimum rotation distance (direct or wrap-around).
- Recursively solve for the rest of the key starting from position
i. - Track the minimum total cost.
- Add
1for the button press at each step. - Return the minimum total from
dfs(0, 0).
class Solution:
def findRotateSteps(self, ring: str, key: str) -> int:
def dfs(r, k):
if k == len(key):
return 0
res = float("inf")
for i, c in enumerate(ring):
if c == key[k]:
min_dist = min(abs(r - i), len(ring) - abs(r - i))
res = min(res, min_dist + 1 + dfs(i, k + 1))
return res
return dfs(0, 0)Time & Space Complexity
- Time complexity:
- Space complexity: for recursion stack.
Where is the length of the and is the length of the .
2. Dynamic Programming (Top-Down)
Intuition
The plain recursion has overlapping subproblems. From the same ring position trying to match the same key index, we always get the same answer. Adding memoization avoids recomputing these states.
The state is defined by two parameters: current ring position and current key index. There are at most n * m unique states, where n is the ring length and m is the key length.
Algorithm
- Create a memoization table
dp[r][k]initialized to-1. - Define
dfs(r, k)that returns the minimum steps from ring positionrto spellkey[k:]. - If
kequals key length, return0. - If
dp[r][k]is already computed, return it. - For each ring position
imatchingkey[k]:- Compute distance as
min(|r - i|, n - |r - i|). - Update the result with
distance + 1 + dfs(i, k + 1).
- Compute distance as
- Store and return
dp[r][k]. - Call
dfs(0, 0)for the final answer.
class Solution:
def findRotateSteps(self, ring: str, key: str) -> int:
n = len(ring)
m = len(key)
dp = {}
def dfs(r, k):
if k == m:
return 0
if (r, k) in dp:
return dp[(r, k)]
res = float("inf")
for i, c in enumerate(ring):
if c == key[k]:
min_dist = min(abs(r - i), n - abs(r - i))
res = min(res, min_dist + 1 + dfs(i, k + 1))
dp[(r, k)] = res
return res
return dfs(0, 0)Time & Space Complexity
- Time complexity:
- Space complexity:
Where is the length of the and is the length of the .
3. Dynamic Programming (Bottom-Up)
Intuition
We can convert the top-down solution to bottom-up by filling the DP table iteratively. Process the key from the last character back to the first. For each key character, compute the minimum cost to reach it from every possible ring position.
The value dp[k][r] represents the minimum steps to spell key[k:] starting from ring position r. We build this by using already-computed values for key[k + 1:].
Algorithm
- Create a 2D DP table of size
(m + 1) x ninitialized to infinity. - Set
dp[m][i] = 0for alli(base case: no more characters to spell). - Iterate
kfromm - 1down to0. - For each ring position
r, find all positionsiwherering[i] == key[k]. - For each matching position, compute:
distance = min(|r - i|, n - |r - i|)dp[k][r] = min(dp[k][r], distance + 1 + dp[k + 1][i])
- Return
dp[0][0].
class Solution:
def findRotateSteps(self, ring: str, key: str) -> int:
n = len(ring)
m = len(key)
dp = [[float("inf")] * n for _ in range(m + 1)]
for i in range(n):
dp[m][i] = 0
for k in range(m - 1, -1, -1):
for r in range(n):
for i in range(n):
if ring[i] == key[k]:
min_dist = min(abs(r - i), n - abs(r - i))
dp[k][r] = min(dp[k][r], min_dist + 1 + dp[k + 1][i])
return dp[0][0]Time & Space Complexity
- Time complexity:
- Space complexity:
Where is the length of the and is the length of the .
4. Dynamic Programming (Space Optimized) - I
Intuition
Since each DP row only depends on the next row, we can reduce space from O(n * m) to O(n) by keeping just two arrays: one for the current key index and one for the next.
Additionally, precomputing the positions of each character in the ring using an adjacency list speeds up lookups.
Algorithm
- Build an adjacency list
adjwhereadj[c]contains all ring positions with characterc. - Initialize
dparray of sizenwith zeros (base case after processing all characters). - Iterate
kfromm - 1down to0. - Create
nextDparray initialized to infinity. - For each ring position
r, look up positions inadj[key[k]]and compute the minimum cost. - Swap
dpandnextDpafter each iteration. - Return
dp[0].
class Solution:
def findRotateSteps(self, ring: str, key: str) -> int:
n = len(ring)
m = len(key)
dp = [0] * n
adj = [[] for _ in range(26)]
for i in range(n):
adj[ord(ring[i]) - ord('a')].append(i)
for k in range(m - 1, -1, -1):
next_dp = [float("inf")] * n
for r in range(n):
for i in adj[ord(key[k]) - ord('a')]:
min_dist = min(abs(r - i), n - abs(r - i))
next_dp[r] = min(next_dp[r], min_dist + 1 + dp[i])
dp = next_dp
return dp[0]Time & Space Complexity
- Time complexity:
- Space complexity:
Where is the length of the and is the length of the .
5. Dynamic Programming (Space Optimized) - II
Intuition
Instead of tracking all ring positions, we can focus only on positions that match key characters. The dp array stores the minimum cost to reach each ring position after matching some prefix of the key.
Initially, we set dp[i] to the distance from position 0 to position i. Then for each subsequent key character, we update only the positions that match, computing the minimum cost by considering transitions from positions matching the previous key character.
Algorithm
- Initialize
dp[i] = min(i, n - i)for each ring position (distance from0). - Build an adjacency list for quick character position lookups.
- For each key index
kfrom1tom - 1:- For each position
rmatchingkey[k], find the minimum cost among all positions matchingkey[k - 1]. - Update
dp[r]with this minimum cost plus the rotation distance.
- For each position
- Find the minimum value among positions matching the last key character.
- Add
mfor all button presses and return.
class Solution:
def findRotateSteps(self, ring: str, key: str) -> int:
n = len(ring)
m = len(key)
dp = [min(i, n - i) for i in range(n)]
adj = [[] for _ in range(26)]
for i in range(n):
adj[ord(ring[i]) - ord('a')].append(i)
for k in range(1, m):
for r in adj[ord(key[k]) - ord('a')]:
min_dist = float("inf")
for i in adj[ord(key[k - 1]) - ord('a')]:
min_dist = min(
min_dist,
min(abs(r - i), n - abs(r - i)) + dp[i]
)
dp[r] = min_dist
return min(dp[i] for i in adj[ord(key[-1]) - ord('a')]) + mTime & Space Complexity
- Time complexity:
- Space complexity:
Where is the length of the and is the length of the .
6. Dynamic Programming (Optimal)
Intuition
For each ring position, we only need to consider the closest matching positions in each direction (clockwise and counterclockwise). Using binary search or maintaining sorted position lists, we can find these two candidates in O(1) amortized time per position.
Since the adjacency list positions are naturally sorted by index, we can use a two-pointer technique while iterating through ring positions. For each position, we find the nearest matching character on either side and choose the better option.
Algorithm
- Precompute sorted position lists for each character.
- Initialize two arrays:
dpfor current state andnextDpfor the next iteration. - For each key character (right to left):
- Use a pointer to track position in the sorted list of matching indices.
- For each ring position
r:- If
ring[r]matches the key character, copy the value fromdp. - Otherwise, find the nearest matching position in each direction using the sorted list.
- Compute minimum cost considering wrap-around distances.
- If
- Swap arrays and continue.
- Return
dp[0] + m.
class Solution:
def findRotateSteps(self, ring: str, key: str) -> int:
n = len(ring)
m = len(key)
dp = [0] * n
next_dp = [0] * n
adj = [[] for _ in range(26)]
for i, c in enumerate(ring):
adj[ord(c) - ord('a')].append(i)
for k in range(m - 1, -1, -1):
c = ord(key[k]) - ord('a')
it, N = 0, len(adj[c])
for r in range(n):
if ord(ring[r]) - ord('a') != c:
next_dp[r] = float('inf')
while it < N and adj[c][it] < r:
it += 1
nextIdx = adj[c][it] if it < N else adj[c][0]
prevIdx = adj[c][it - 1] if it > 0 else adj[c][-1]
next_dp[r] = min(
(r - prevIdx if r > prevIdx else n - (prevIdx - r)) + dp[prevIdx],
(nextIdx - r if nextIdx > r else n - (r - nextIdx)) + dp[nextIdx]
)
else:
next_dp[r] = dp[r]
dp, next_dp = next_dp, dp
return dp[0] + mTime & Space Complexity
- Time complexity:
- Space complexity:
Where is the length of the and is the length of the .
Common Pitfalls
Forgetting the Ring is Circular
The distance between two positions on the ring should consider both clockwise and counterclockwise directions. The minimum distance is min(|i - j|, n - |i - j|). Using only the absolute difference ignores the wrap-around path, which may be shorter.
Not Counting Button Presses
Each character in the key requires one button press after rotating to the correct position. A common mistake is only counting rotation steps and forgetting to add 1 for each character, or adding the total m button presses incorrectly.
Missing Memoization in Recursive Solutions
Without memoization, the recursive solution has exponential time complexity because the same (ring position, key index) states are recomputed many times. The state space is only O(n * m), so caching results is essential for efficiency.
Considering Only One Matching Position
When a character appears multiple times in the ring, you must consider all occurrences and choose the one that minimizes total cost. Greedily picking the closest matching position without considering future characters leads to suboptimal solutions.
Incorrect State Transition in Bottom-Up DP
In bottom-up approaches, the order of iteration matters. Processing from the last key character backwards and correctly propagating the minimum costs to earlier states is crucial. Reversing the direction or incorrectly indexing the DP table produces wrong answers.
Sign in to join the discussion