Freedom Trail

class Solution {
public:
    int findRotateSteps(string ring, string key) {
        int R = ring.size(), K = key.size();
        vector<vector<int>> positions(26);
        for (int i = 0; i < R; ++i) positions[ring[i] - 'a'].push_back(i);
        vector<int> dp(R, 0);
        for (int k = K - 1; k >= 0; --k) {
            vector<int> nd(R, INT_MAX);
            for (int i = 0; i < R; ++i) {
                for (int j : positions[key[k] - 'a']) {
                    int rot = min(abs(i - j), R - abs(i - j));
                    nd[i] = min(nd[i], rot + 1 + dp[j]);
                }
            }
            dp = nd;
        }
        return dp[0];
    }
};

import "math"

func findRotateSteps(ring string, key string) int {
    R, K := len(ring), len(key)
    positions := make([][]int, 26)
    for i := 0; i < R; i++ {
        positions[ring[i]-'a'] = append(positions[ring[i]-'a'], i)
    }
    abs := func(x int) int {
        if x < 0 {
            return -x
        }
        return x
    }
    dp := make([]int, R)
    for k := K - 1; k >= 0; k-- {
        nd := make([]int, R)
        for i := range nd {
            nd[i] = math.MaxInt32
        }
        for i := 0; i < R; i++ {
            for _, j := range positions[key[k]-'a'] {
                d := abs(i - j)
                rot := d
                if R-d < rot {
                    rot = R - d
                }
                cost := rot + 1 + dp[j]
                if cost < nd[i] {
                    nd[i] = cost
                }
            }
        }
        dp = nd
    }
    return dp[0]
}

from typing import List

class Solution:
    def findRotateSteps(self, ring: str, key: str) -> int:
        R, K = len(ring), len(key)
        positions: List[List[int]] = [[] for _ in range(26)]
        for i, ch in enumerate(ring):
            positions[ord(ch) - ord('a')].append(i)
        INF = float('inf')
        dp = [0] * R
        for k in range(K - 1, -1, -1):
            nd = [INF] * R
            for i in range(R):
                for j in positions[ord(key[k]) - ord('a')]:
                    d = abs(i - j)
                    rot = min(d, R - d)
                    cost = rot + 1 + dp[j]
                    if cost < nd[i]:
                        nd[i] = cost
            dp = nd
        return dp[0]

var findRotateSteps = function(ring, key) {
    const R = ring.length, K = key.length;
    const A = 'a'.charCodeAt(0);
    const positions = Array.from({ length: 26 }, () => []);
    for (let i = 0; i < R; i++) positions[ring.charCodeAt(i) - A].push(i);
    let dp = new Array(R).fill(0);
    for (let k = K - 1; k >= 0; k--) {
        const nd = new Array(R).fill(Infinity);
        for (let i = 0; i < R; i++) {
            for (const j of positions[key.charCodeAt(k) - A]) {
                const d = Math.abs(i - j);
                const rot = Math.min(d, R - d);
                const cost = rot + 1 + dp[j];
                if (cost < nd[i]) nd[i] = cost;
            }
        }
        dp = nd;
    }
    return dp[0];
};

class Solution {
    public int findRotateSteps(String ring, String key) {
        int R = ring.length(), K = key.length();
        List<List<Integer>> positions = new ArrayList<>();
        for (int i = 0; i < 26; i++) positions.add(new ArrayList<>());
        for (int i = 0; i < R; i++) positions.get(ring.charAt(i) - 'a').add(i);
        int[] dp = new int[R];
        for (int k = K - 1; k >= 0; k--) {
            int[] nd = new int[R];
            Arrays.fill(nd, Integer.MAX_VALUE);
            for (int i = 0; i < R; i++) {
                for (int j : positions.get(key.charAt(k) - 'a')) {
                    int d = Math.abs(i - j);
                    int rot = Math.min(d, R - d);
                    int cost = rot + 1 + dp[j];
                    if (cost < nd[i]) nd[i] = cost;
                }
            }
            dp = nd;
        }
        return dp[0];
    }
}

function findRotateSteps(ring: string, key: string): number {
    const R = ring.length, K = key.length;
    const A = 'a'.charCodeAt(0);
    const positions: number[][] = Array.from({ length: 26 }, () => []);
    for (let i = 0; i < R; i++) positions[ring.charCodeAt(i) - A].push(i);
    let dp: number[] = new Array(R).fill(0);
    for (let k = K - 1; k >= 0; k--) {
        const nd: number[] = new Array(R).fill(Infinity);
        for (let i = 0; i < R; i++) {
            for (const j of positions[key.charCodeAt(k) - A]) {
                const d = Math.abs(i - j);
                const rot = Math.min(d, R - d);
                const cost = rot + 1 + dp[j];
                if (cost < nd[i]) nd[i] = cost;
            }
        }
        dp = nd;
    }
    return dp[0];
}