We can further improve the runtime of this DP Solution from `O(R * R * K)`

to `O(R * (26 + K)) = O(RK)`

, where `R = |Ring|`

and `K = |Key|`

. Basically, we can do the inner-most loop in `O(1)`

time. The idea is that if we are currently at position `i`

and require the previous char equal to some letter `ch`

, we just need to check the position (with letter `ch`

) that is closest to `i`

from its left or right. Thus, at most two positions need to be checked, instead of the entire ring.

**Update:** The preprocessing of the following code takes `O(R^2 * 26) = O(R^2)`

time. But I believe there must exist a faster way, and ~~I was just too lazy to do that~~...

**Update:** Okay, the preprocessing can be done in `O(26 * R) = O(R)`

time.

```
public int findRotateSteps(String ring, String key) {
int R = ring.length(), K = key.length();
int[][] prev = new int[R][26], next = new int[R][26];
for (int i = 0; i < R; i++) {
Arrays.fill(prev[i], -1);
Arrays.fill(next[i], -1);
for (int j = (i + 1) % R; j != i; j = (j + 1) % R) {
int ch = ring.charAt(j) - 'a';
if (next[i][ch] == -1) next[i][ch] = j;
}
for (int j = (i - 1 + R) % R; j != i; j = (j - 1 + R) % R) {
int ch = ring.charAt(j) - 'a';
if (prev[i][ch] == -1) prev[i][ch] = j;
}
prev[i][ring.charAt(i) - 'a'] = next[i][ring.charAt(i) - 'a'] = i;
}
int[][] f = new int[K][R];
int ans = Integer.MAX_VALUE;
for (int i = 0; i < K; i++) {
for (int j = 0; j < R; j++) {
f[i][j] = Integer.MAX_VALUE / 2;
if (key.charAt(i) == ring.charAt(j)) {
if (i == 0) f[i][j] = Math.min(f[i][j], dist(0, j, ring.length()));
else {
int preKey = key.charAt(i - 1) - 'a';
f[i][j] = Math.min(f[i][j], f[i - 1][prev[j][preKey]] + dist(prev[j][preKey], j, ring.length()));
f[i][j] = Math.min(f[i][j], f[i - 1][next[j][preKey]] + dist(next[j][preKey], j, ring.length()));
}
}
if (i == K - 1) ans = Math.min(ans, f[i][j]);
}
}
return ans + K;
}
```

An `O(26R) = O(R)`

-time preprocessing.

```
int R = ring.length(), K = key.length();
int[][] prev = new int[R][26], next = new int[R][26];
Map<Character, List<Integer>> map = new HashMap<>();
for (int i = 0; i < ring.length(); i++) {
char ch = ring.charAt(i);
map.putIfAbsent(ch, new ArrayList<>());
map.get(ch).add(i);
}
for (char ch : map.keySet()) {
List<Integer> list = map.get(ch);
for (int i = 0, ptr = 0; i < ring.length(); i++) {
next[i][ch - 'a'] = list.get(ptr);
prev[i][ch - 'a'] = list.get((ptr - 1 + list.size()) % list.size());
if (ring.charAt(i) == ch) ptr = (ptr + 1) % list.size();
}
}
```