Freedom Trail — Solution in Python, Java & C++
Freedom Trail solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem, asked at Amazon and Google.
Freedom Trail is a hard coding problem on strings, dynamic programming and depth-first search, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Strings, Dynamic Programming, Depth-First Search, Breadth-First Search
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A circular dial has the characters of ring engraved around its edge, in order. One position, the 12:00 mark, is special; at the start, ring[0] is aligned with it.
To spell a word key, you enter its characters one by one. For each character you:
- rotate the ring clockwise or anticlockwise, one position per step, until some occurrence of that character sits at 12:00, and then
- press the centre button, which also counts as one step.
Return the minimum total number of steps to spell all of key. It is guaranteed that every character of key appears somewhere in ring.
Example 1
Input: ring = "godding", key = "gd"
Output: 4
Explanation: 'g' is already at 12:00: press (1 step). Rotate anticlockwise two positions to the 'd' at index 5 (2 steps) and press (1 step).
Example 2
Input: ring = "godding", key = "godding"
Output: 13
Example 3
Input: ring = "a", key = "aaa"
Output: 3
Explanation: Only the three button presses.
Constraints
1 <= ring.length, key.length <= 100ring and key consist of lowercase English lettersevery character of key occurs in ring
Hints for Freedom Trail
Hint 1
Greedily rotating to the nearest copy of each character can be wrong — the copy you stop at affects the cost of every later character.
Hint 2
After spelling
key[0..i], all that matters for the future is which index ofringis at 12:00. That suggests a DP over (characters spelled, ring position).Hint 3
Let
cost[p]be the cheapest way to have just pressed at ring positionp. For the next character, every positionqholding it getsmin over p of cost[p] + dist(p, q)withdist = min(|p - q|, n - |p - q|). Add one press per character.
How to solve Freedom Trail
The state of the dial between characters is just the index aligned with 12:00. For each character of key, the dial must end at one of that character's positions, and the cheapest way to get there depends only on where it was after the previous character — a layered shortest-path / DP over positions.
Approach
- Group the indices of
ringby character. - Start with
cost = {0: 0}(index 0 at 12:00, nothing spent). - For each character
cofkey: for every indexqwithring[q] == c,next[q] = min over previous p of cost[p] + min(|p - q|, n - |p - q|). Replacecostbynext. - Return
min(cost) + key.length— each character also costs one press.
Why it works
Rotating between two alignments costs exactly their circular distance, and the shortest way to spell key[0..i] ending at q must spell key[0..i-1] optimally ending at some p and then rotate from p to q. Taking the minimum over all p covers every possibility, so each layer is exact, and the last layer's minimum is the answer.
Complexity
- Time —
O(k * n^2) in the worst case (O(k * a * b) for the sizes of consecutive character groups) - Space —
O(n)
Pitfalls
- Choosing the nearest occurrence greedily: in "godding" the two 'd's and two 'g's make that sub-optimal on some keys.
- The rotation is circular — the distance is
min(d, n - d), notd. - Don't forget the button press for every character, including repeated ones that need no rotation.
Reference solution
Python
def findRotateSteps(ring: str, key: str) -> int:
n = len(ring)
where = {}
for i, ch in enumerate(ring):
where.setdefault(ch, []).append(i)
cost = {0: 0}
for ch in key:
nxt = {}
for q in where[ch]:
best = None
for p, c in cost.items():
d = abs(p - q)
cand = c + min(d, n - d)
if best is None or cand < best:
best = cand
nxt[q] = best
cost = nxt
return min(cost.values()) + len(key)Java
public static int findRotateSteps(String ring, String key) {
int n = ring.length();
final int INF = 1000000000;
int[] cost = new int[n];
Arrays.fill(cost, INF);
cost[0] = 0;
for (int i = 0; i < key.length(); i++) {
int[] next = new int[n];
Arrays.fill(next, INF);
char c = key.charAt(i);
for (int q = 0; q < n; q++) {
if (ring.charAt(q) != c) continue;
for (int p = 0; p < n; p++) {
if (cost[p] == INF) continue;
int d = Math.abs(p - q);
next[q] = Math.min(next[q], cost[p] + Math.min(d, n - d));
}
}
cost = next;
}
int best = INF;
for (int v : cost) best = Math.min(best, v);
return best + key.length();
}C++
int findRotateSteps(string ring, string key) {
int n = ring.size();
const int INF = 1000000000;
vector<int> cost(n, INF);
cost[0] = 0;
for (char c : key) {
vector<int> next(n, INF);
for (int q = 0; q < n; q++) {
if (ring[q] != c) continue;
for (int p = 0; p < n; p++) {
if (cost[p] == INF) continue;
int d = abs(p - q);
next[q] = min(next[q], cost[p] + min(d, n - d));
}
}
cost = next;
}
return *min_element(cost.begin(), cost.end()) + (int) key.size();
}JavaScript
var findRotateSteps = function(ring, key) {
var n = ring.length;
var INF = 1e9;
var cost = new Array(n).fill(INF);
cost[0] = 0;
for (var i = 0; i < key.length; i++) {
var next = new Array(n).fill(INF);
for (var q = 0; q < n; q++) {
if (ring.charAt(q) !== key.charAt(i)) continue;
for (var p = 0; p < n; p++) {
if (cost[p] === INF) continue;
var d = Math.abs(p - q);
var cand = cost[p] + Math.min(d, n - d);
if (cand < next[q]) next[q] = cand;
}
}
cost = next;
}
var best = INF;
for (var k = 0; k < n; k++) if (cost[k] < best) best = cost[k];
return best + key.length;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Dynamic Programming