Freedom Trail

How it works

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.

Steps

1. Precompute sorted position lists for each character.
2. Initialize two arrays: dp for current state and nextDp for the next iteration.
3. 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.
4. Swap arrays and continue.
5. Return dp[0] + m.

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.

Things to watch for

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.

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

class Solution {
public:
    int findRotateSteps(string ring, string key) {
        int n = ring.size(), m = key.size();

        vector<int> dp(n, 0);
        vector<int> nextDp(n, 0);
        vector<vector<int>> adj(26);

        for (int i = 0; i < n; i++) {
            adj[ring[i] - 'a'].push_back(i);
        }

        for (int k = m - 1; k >= 0; k--) {
            int c = key[k] - 'a';
            int it = 0, N = adj[c].size();

            for (int r = 0; r < n; r++) {
                if (ring[r] - 'a' != c) {
                    nextDp[r] = INT_MAX;
                    while (it < N && adj[c][it] < r) {
                        it++;
                    }

                    int nextIdx = it < N ? adj[c][it] : adj[c][0];
                    int prevIdx = it > 0 ? adj[c][it - 1] : adj[c][N - 1];

                    nextDp[r] = min(
                        (r > prevIdx ? r - prevIdx : n - (prevIdx - r)) + dp[prevIdx],
                        (nextIdx > r ? nextIdx - r : n - (r - nextIdx)) + dp[nextIdx]
                    );
                } else {
                    nextDp[r] = dp[r];
                }
            }

            dp.swap(nextDp);
        }

        return dp[0] + m;
    }
};