Freedom Trail

Hard
1616.

Freedom Trail

Freedom Trail is a hard coding problem on strings, dynamic programming and depth-first search, asked in Amazon and Google interviews.

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:

  1. rotate the ring clockwise or anticlockwise, one position per step, until some occurrence of that character sits at 12:00, and then
  2. 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 <= 100
  • ring and key consist of lowercase English letters
  • every character of key occurs in ring
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} ring
 * @param {string} key
 * @return {number}
 */
var findRotateSteps = function(ring, key) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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:

  1. rotate the ring clockwise or anticlockwise, one position per step, until some occurrence of that character sits at 12:00, and then
  2. 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 <= 100
  • ring and key consist of lowercase English letters
  • every character of key occurs in ring

Hints for Freedom Trail

  1. 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.

  2. Hint 2

    After spelling key[0..i], all that matters for the future is which index of ring is at 12:00. That suggests a DP over (characters spelled, ring position).

  3. Hint 3

    Let cost[p] be the cheapest way to have just pressed at ring position p. For the next character, every position q holding it gets min over p of cost[p] + dist(p, q) with dist = 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

  1. Group the indices of ring by character.
  2. Start with cost = {0: 0} (index 0 at 12:00, nothing spent).
  3. For each character c of key: for every index q with ring[q] == c, next[q] = min over previous p of cost[p] + min(|p - q|, n - |p - q|). Replace cost by next.
  4. 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), not d.
  • 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