You are given a circular ring represented by a string ring and a key represented by another string key. The ring consists of lowercase English letters arranged in a circle, and you can rotate the ring clockwise or counterclockwise one position at a time. Each rotation counts as one step. To select a character, you press a button at the current position (which also counts as one step). The initial position is at index 0 of the ring.
Your task is to find the minimum number of steps required to spell all the characters in key in order, by rotating the ring and pressing the button to select each character. You can rotate the ring in either direction, and you must spell the key in order—no skipping or reordering.
Constraints:
key must be selected in order.ring.
At first glance, the problem seems to invite a brute-force approach: for every character in key, rotate the ring to every possible position containing that character, and recursively try all options. However, this quickly becomes infeasible for longer rings and keys due to the exponential number of possibilities.
The key insight is to recognize overlapping subproblems: the state of the ring after spelling a prefix of the key can be reused if we reach the same position again. This suggests using dynamic programming or memoization to avoid recomputation.
Instead of simulating every rotation, we can precompute the positions of each character in ring and, for each character in key, only consider rotating directly to the next occurrence. By caching results for each combination of ring position and key index, we can efficiently explore all possibilities.
ring to all its positions. This allows us to quickly find where the next character in key appears.
ring), and the current index in key we are trying to spell.
ring. For each, calculate the minimal rotation distance from the current position (either clockwise or counterclockwise), add one for the button press, and recursively solve for the next character starting from this new position.
key, return 0 (no more steps needed).
We use memoization (e.g., functools.lru_cache in Python, or a hash map in other languages) to avoid recomputing results for the same state.
Sample Input:
ring = "godding", key = "gd"
ring.
The function would try all possible positions for each character, but memoization ensures we only compute each unique state once.
key because for each character, we may try each position in ring where it appears, leading to O(n^m) time where n is the length of ring and m is the length of key.
ring and m is the length of key. For each state, we consider at most n transitions (all positions for a character), so the total time is O(n^2 * m) in the worst case.
The "Freedom Trail" problem is a classic example of optimizing a process with overlapping subproblems and multiple choices at each step. By mapping characters to their positions and using dynamic programming (memoization), we avoid redundant computations and efficiently find the minimum steps required. The solution elegantly combines preprocessing, state definition, and recursion, demonstrating the power of DP for sequence and rotation problems.
from collections import defaultdict
from functools import lru_cache
class Solution:
def findRotateSteps(self, ring: str, key: str) -> int:
n = len(ring)
pos = defaultdict(list)
for i, c in enumerate(ring):
pos[c].append(i)
@lru_cache(maxsize=None)
def dp(i, j):
# i: current position in ring
# j: current position in key
if j == len(key):
return 0
res = float('inf')
for k in pos[key[j]]:
delta = abs(i - k)
step = min(delta, n - delta) + 1 # rotation + select
res = min(res, step + dp(k, j + 1))
return res
return dp(0, 0)
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>
using namespace std;
class Solution {
public:
int findRotateSteps(string ring, string key) {
int n = ring.size(), m = key.size();
unordered_map<char, vector<int>> pos;
for (int i = 0; i < n; ++i)
pos[ring[i]].push_back(i);
vector<vector<int>> memo(n, vector<int>(m, -1));
function<int(int, int)> dp = [&](int i, int j) {
if (j == m) return 0;
if (memo[i][j] != -1) return memo[i][j];
int res = INT_MAX;
for (int k : pos[key[j]]) {
int delta = abs(i - k);
int step = min(delta, n - delta) + 1;
res = min(res, step + dp(k, j + 1));
}
return memo[i][j] = res;
};
return dp(0, 0);
}
};
import java.util.*;
class Solution {
public int findRotateSteps(String ring, String key) {
int n = ring.length(), m = key.length();
Map<Character, List<Integer>> pos = new HashMap<>();
for (int i = 0; i < n; ++i) {
pos.computeIfAbsent(ring.charAt(i), k -> new ArrayList<>()).add(i);
}
int[][] memo = new int[n][m];
for (int[] row : memo) Arrays.fill(row, -1);
return dp(0, 0, ring, key, pos, memo);
}
private int dp(int i, int j, String ring, String key, Map<Character, List<Integer>> pos, int[][] memo) {
if (j == key.length()) return 0;
if (memo[i][j] != -1) return memo[i][j];
int n = ring.length();
int res = Integer.MAX_VALUE;
for (int k : pos.get(key.charAt(j))) {
int delta = Math.abs(i - k);
int step = Math.min(delta, n - delta) + 1;
res = Math.min(res, step + dp(k, j + 1, ring, key, pos, memo));
}
memo[i][j] = res;
return res;
}
}
var findRotateSteps = function(ring, key) {
const n = ring.length, m = key.length;
const pos = {};
for (let i = 0; i < n; ++i) {
if (!pos[ring[i]]) pos[ring[i]] = [];
pos[ring[i]].push(i);
}
const memo = Array.from({length: n}, () => Array(m).fill(-1));
function dp(i, j) {
if (j === m) return 0;
if (memo[i][j] !== -1) return memo[i][j];
let res = Infinity;
for (const k of pos[key[j]]) {
const delta = Math.abs(i - k);
const step = Math.min(delta, n - delta) + 1;
res = Math.min(res, step + dp(k, j + 1));
}
memo[i][j] = res;
return res;
}
return dp(0, 0);
};