#514

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Freedom Trail

Determine the minimum rotations and button presses to spell a keyword on a circular dial using state transition dynamic programming.

string dynamic programming depth first search breadth first search

Problem Statement

In Fallout 4's "Road to Freedom" quest, players encounter a circular metal dial called the Freedom Trail Ring engraved with letters. The goal is to spell a given keyword by rotating the ring clockwise or anticlockwise so each character aligns at the 12:00 position, followed by pressing the center button.

Given a string ring representing the letters on the dial and a string key representing the keyword, calculate the minimum number of steps required to spell all characters in key in order. Each rotation counts as one step, and pressing a character counts as an additional step. The first character of the ring starts aligned at 12:00.

Examples

Example 1

Input: ring = "godding", key = "gd"

Output: 4

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

Example details omitted.

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.

Solution Approach

Map Characters to Positions

Preprocess the ring to record all indices for each character. This allows constant-time lookup for target positions when transitioning between key characters, a critical step for state transition dynamic programming efficiency.

Dynamic Programming State Definition

Define dp[i][j] as the minimal steps to spell the first i characters of key with ring[j] aligned at 12:00. Transition by considering all positions of the next key character and compute the rotation distance clockwise and anticlockwise plus the button press.

Iterate and Minimize

For each key character, iterate over all possible ring positions from the previous DP state, calculate total steps for reaching each target character, and update dp with the minimal value. After processing all key characters, select the minimum from the last row as the final result.

Complexity Analysis

Metric	Value
Time	O(RK \cdot \log (RK))
Space	O(R \cdot K)

Time complexity is O(RK * log(RK)) due to iterating over ring positions for each key character and computing minimal rotations. Space complexity is O(R * K) to store DP states for all ring indices and key positions.

What Interviewers Usually Probe

Look for proper DP state definition and transitions when the candidate writes code.
Check if the candidate optimizes rotations both clockwise and anticlockwise.
Confirm the solution avoids recomputation by correctly mapping characters to multiple positions.

Common Pitfalls or Variants

Common pitfalls

Failing to account for both clockwise and anticlockwise rotation distances.
Not preprocessing ring characters to multiple indices, causing slow transitions.
Incorrectly initializing DP states leading to overcounting steps or misaligned characters.

Follow-up variants

Allow a ring with repeated characters but a longer key to test DP efficiency.
Consider a key that includes characters not in the initial 12:00 alignment to stress rotations.
Use a ring of maximum length (100) and a key with maximum length (100) to evaluate space optimization.

FAQ

What is the best approach to solve Freedom Trail?

Use state transition dynamic programming to track minimum steps for each key character while considering all positions on the ring.

How do I calculate rotation steps efficiently?

Compute both clockwise and anticlockwise distances between current and target positions, then add one step for pressing the button.

Can characters appear multiple times on the ring?

Yes, and preprocessing all indices of each character allows DP to select the minimal rotation path for every key character.

What is the time complexity of the optimal solution?

It is O(RK * log(RK)), where R is ring length and K is key length, because each DP transition considers all positions with minimal rotation.

Why is this problem called a state transition DP pattern?

Because the solution tracks the minimal steps for each key character while transitioning between all feasible ring positions, typical of state transition dynamic programming.

terminal

Solution

Solution 1: Dynamic Programming

First, we preprocess the positions of each character $c$ in the string $ring$, and record them in the array $pos[c]$. Suppose the lengths of the strings $key$ and $ring$ are $m$ and $n$, respectively.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

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

Continue Practicing

#488 zuma game #472 concatenated words #449 serialize and deserialize bst