Freedom Trail

hard string dp dfs bfs

Problem

Ring is a string of lowercase letters. key is the word you must spell. Rotation cost 1 each step (either direction); each spell costs 1. Return min total cost.

Inputring = "godding", key = "gd"

Output4

DP scans key from right to left, picking the best ring position per character.

ring

key

def find_rotate_steps(ring, key):
    from collections import defaultdict
    n, m = len(ring), len(key)
    pos = defaultdict(list)
    for i, c in enumerate(ring): pos[c].append(i)
    INF = float("inf")
    dp = [INF] * n; dp[0] = 0
    def dist(a, b): return min(abs(a - b), n - abs(a - b))
    cur = {0: 0}
    for c in key:
        nxt = {}
        for j in pos[c]:
            best = INF
            for p, v in cur.items():
                best = min(best, v + dist(p, j) + 1)
            nxt[j] = best
        cur = nxt
    return min(cur.values())

function findRotateSteps(ring, key) {
  const n = ring.length;
  const pos = {};
  for (let i = 0; i < n; i++) (pos[ring[i]] ??= []).push(i);
  const dist = (a, b) => Math.min(Math.abs(a - b), n - Math.abs(a - b));
  let cur = new Map([[0, 0]]);
  for (const c of key) {
    const next = new Map();
    for (const j of pos[c]) {
      let best = Infinity;
      for (const [p, v] of cur) best = Math.min(best, v + dist(p, j) + 1);
      next.set(j, best);
    }
    cur = next;
  }
  return Math.min(...cur.values());
}

class Solution {
    public int findRotateSteps(String ring, String key) {
        int n = ring.length();
        Map> pos = new HashMap<>();
        for (int i = 0; i < n; i++) pos.computeIfAbsent(ring.charAt(i), k -> new ArrayList<>()).add(i);
        Map cur = new HashMap<>(); cur.put(0, 0);
        for (char c : key.toCharArray()) {
            Map next = new HashMap<>();
            for (int j : pos.get(c)) {
                int best = Integer.MAX_VALUE;
                for (var e : cur.entrySet()) {
                    int d = Math.min(Math.abs(e.getKey() - j), n - Math.abs(e.getKey() - j));
                    best = Math.min(best, e.getValue() + d + 1);
                }
                next.put(j, best);
            }
            cur = next;
        }
        return Collections.min(cur.values());
    }
}

int findRotateSteps(string ring, string key) {
    int n = ring.size();
    unordered_map> pos;
    for (int i = 0; i < n; i++) pos[ring[i]].push_back(i);
    unordered_map cur{{0, 0}};
    for (char c : key) {
        unordered_map next;
        for (int j : pos[c]) {
            int best = INT_MAX;
            for (auto& [p, v] : cur) {
                int d = min(abs(p - j), n - abs(p - j));
                best = min(best, v + d + 1);
            }
            next[j] = best;
        }
        cur = next;
    }
    int ans = INT_MAX;
    for (auto& [_, v] : cur) ans = min(ans, v);
    return ans;
}

Explanation

You spell key one letter at a time by rotating a circular ring so the right letter sits at 12 o'clock, then pressing it. A letter may appear at several ring positions, and which one you pick changes how far you must rotate for the next letter. So we track the best cost to be at each possible position.

We keep a map cur from "ring position" to "minimum cost to have just typed the current letter from there." We start at position 0 with cost 0.

For each character of key, we look at every ring position j that holds that letter. The cost to land on j is the best over all previous positions p: cur[p] + dist(p, j) + 1, where dist is the shorter way around the circle and the +1 is the button press.

The circular distance is min(|a - b|, n - |a - b|) because you can rotate either direction. After processing all of key, the answer is the smallest value left in cur.

Example: ring = "godding", key = "gd". There are two gs and two ds, so the DP weighs all the rotate options and finds the cheapest total, which is 4.

Time: O(|ring|·|key|·k) Space: O(|ring|)