Note:

DP means we have (i, end) keys and starting from j position how many "STEPS" we need. This does not include press button step.

class Solution {    public int findRotateSteps(String ring, String key) {        int[][] dp = new int[key.length() + 1][ring.length()];        for (int i = key.length() - 1; i >= 0; i--) {            for (int j = 0; j < ring.length(); j++) {                dp[i][j] = Integer.MAX_VALUE;                for (int k = 0; k < ring.length(); k++) {                    if (key.charAt(i) == ring.charAt(k)) {                        int diff = Math.abs(j - k);                        int step = Math.min(diff, ring.length() - diff);                        dp[i][j] = Math.min(dp[i][j], dp[i + 1][k] + step);                    }                }            }        }        return dp[0][0] + key.length();    }}