514. Freedom Trail - Explanation

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) where r is the current ring position and k is the current index in the key.
Base case: if k equals the key length, return 0.
For each position i in the ring where ring[i] matches key[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 1 for 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: $O(n ^ m)$
Space complexity: $O(m)$ for recursion stack.

Where $n$ is the length of the $ring$ and $m$ is the length of the $key$ .

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 position r to spell key[k:].
If k equals key length, return 0.
If dp[r][k] is already computed, return it.
For each ring position i matching key[k]:
- Compute distance as min(|r - i|, n - |r - i|).
- Update the result with distance + 1 + dfs(i, k + 1).
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: $O(n ^ 2 * m)$
Space complexity: $O(n * m)$

Where $n$ is the length of the $ring$ and $m$ is the length of the $key$ .

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 n initialized to infinity.
Set dp[m][i] = 0 for all i (base case: no more characters to spell).
Iterate k from m - 1 down to 0.
For each ring position r, find all positions i where ring[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: $O(n ^ 2 * m)$
Space complexity: $O(n * m)$

Where $n$ is the length of the $ring$ and $m$ is the length of the $key$ .

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 adj where adj[c] contains all ring positions with character c.
Initialize dp array of size n with zeros (base case after processing all characters).
Iterate k from m - 1 down to 0.
Create nextDp array initialized to infinity.
For each ring position r, look up positions in adj[key[k]] and compute the minimum cost.
Swap dp and nextDp after 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: $O(n ^ 2 * m)$
Space complexity: $O(n)$

Where $n$ is the length of the $ring$ and $m$ is the length of the $key$ .

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 from 0).
Build an adjacency list for quick character position lookups.
For each key index k from 1 to m - 1:
- For each position r matching key[k], find the minimum cost among all positions matching key[k - 1].
- Update dp[r] with this minimum cost plus the rotation distance.
Find the minimum value among positions matching the last key character.
Add m for 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')]) + m

Time & Space Complexity

Time complexity: $O(n ^ 2 * m)$
Space complexity: $O(n)$

Where $n$ is the length of the $ring$ and $m$ is the length of the $key$ .

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: dp for current state and nextDp for 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 from dp.
  - Otherwise, find the nearest matching position in each direction using the sorted list.
  - Compute minimum cost considering wrap-around distances.
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] + m

Time & Space Complexity

Time complexity: $O(n * m)$
Space complexity: $O(n)$

Where $n$ is the length of the $ring$ and $m$ is the length of the $key$ .

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.