<p>In the video game Fallout 4, the quest <strong>&quot;Road to Freedom&quot;</strong> requires players to reach a metal dial called the <strong>&quot;Freedom Trail Ring&quot;</strong> and use the dial to spell a specific keyword to open the door.</p>

<p>Given a string <code>ring</code> that represents the code engraved on the outer ring and another string <code>key</code> that represents the keyword that needs to be spelled, return <em>the minimum number of steps to spell all the characters in the keyword</em>.</p>

<p>Initially, the first character of the ring is aligned at the <code>&quot;12:00&quot;</code> direction. You should spell all the characters in <code>key</code> one by one by rotating <code>ring</code> clockwise or anticlockwise to make each character of the string key aligned at the <code>&quot;12:00&quot;</code> direction and then by pressing the center button.</p>

<p>At the stage of rotating the ring to spell the key character <code>key[i]</code>:</p>

<ol>
	<li>You can rotate the ring clockwise or anticlockwise by one place, which counts as <strong>one step</strong>. The final purpose of the rotation is to align one of <code>ring</code>&#39;s characters at the <code>&quot;12:00&quot;</code> direction, where this character must equal <code>key[i]</code>.</li>
	<li>If the character <code>key[i]</code> has been aligned at the <code>&quot;12:00&quot;</code> direction, press the center button to spell, which also counts as <strong>one step</strong>. After the pressing, you could begin to spell the next character in the key (next stage). Otherwise, you have finished all the spelling.</li>
</ol>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img src="https://assets.leetcode.com/uploads/2018/10/22/ring.jpg" style="width: 450px; height: 450px;" />
<pre>
<strong>Input:</strong> ring = &quot;godding&quot;, key = &quot;gd&quot;
<strong>Output:</strong> 4
<strong>Explanation:</strong>
For the first key character &#39;g&#39;, since it is already in place, we just need 1 step to spell this character. 
For the second key character &#39;d&#39;, we need to rotate the ring &quot;godding&quot; anticlockwise by two steps to make it become &quot;ddinggo&quot;.
Also, we need 1 more step for spelling.
So the final output is 4.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> ring = &quot;godding&quot;, key = &quot;godding&quot;
<strong>Output:</strong> 13
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= ring.length, key.length &lt;= 100</code></li>
	<li><code>ring</code> and <code>key</code> consist of only lower case English letters.</li>
	<li>It is guaranteed that <code>key</code> could always be spelled by rotating <code>ring</code>.</li>
</ul>

// f(i, j) = minimum number of steps to spell key[j..)
//              assuming we start with a ring rotated clockwise
//              i times (i.e., ring[i] is at 12:00)

//
// clockwise(i, c) = first occurrence of character c rotating
//                      clockwise starting with ring[i] at 12:00
//
// anticlockwise(i, c) = first occurrence of character c rotating
//                          anticlockwise starting with ring[i] at 12:00
//
// f(i, j) = find closest occurrence of key[j] by rotating
//              ring in either direction, and take the one that
//              minimizes f(., j + 1)
//          = 1 + min(f(clockwise(i, c), j + 1), f(anticlockwise(i, c), j + 1))
// 
// f(i, m) = 0     

// n = |ring|
// m = |key|
// Time:
//  - Computing clockwise and anticlockwise takes O(n) time (there are O(1) lowercase English letters)
//  - Computing f takes O(nm) with DP
// Space: O(n)

ostream& operator<<(ostream& out, const vector<unordered_map<char, int>>& v) {
    for (int i = 0; i < v.size(); ++i) {
        out << "v[" << i << "] = { ";
        for (auto kv : v[i]) {
            out << "(" << kv.first << "," << kv.second << ")";
        }
        out << endl;
    }
    return out;
}

class Solution {
public:
    vector<unordered_map<char, int>> computeClockwiseDistances(string& ring) {
        int n = ring.size();
        vector<unordered_map<char, int>> res(n);
        unordered_set<char> alphabet;
        for (int i = 0; i < n; ++i) {
            char c = ring[i];
            if (res[0].count(c) == 0) {
                res[0][c] = i;
            }
            alphabet.insert(c);
        }
        for (int i = n - 1; i >= 1; --i) {
            for (auto c : alphabet) {
                res[i][c] = (ring[i] == c) ? i : res[(i + 1) % n][c];
            }
        }
        return res;
    }

    void fix(vector<unordered_map<char, int>>& anticlockwise) {
        reverse(anticlockwise.begin(), anticlockwise.end());
        int n = anticlockwise.size();
        for (int i = 0; i < n; ++i) {
            for (auto kv : anticlockwise[i]) {
                anticlockwise[i][kv.first] = n - kv.second - 1; 
            }
        }
    }

    int findRotateSteps(string ring, string key) {
        int n = ring.size();
        int m = key.size();
        vector<unordered_map<char, int>> clockwise = computeClockwiseDistances(ring);
        string reversed = ring;
        reverse(reversed.begin(), reversed.end());
        vector<unordered_map<char, int>> anticlockwise = computeClockwiseDistances(reversed);
        fix(anticlockwise);

        cout << clockwise << endl;
        cout << anticlockwise << endl;

        vector<int> prev(n);
        vector<int> next(n, 0);
        for (int j = m - 1; j >= 0; --j) {
            prev = next;
            for (int i = 0; i < n; ++i) {
                int cw;
                if (clockwise[i][key[j]] >= i) {
                    cw = clockwise[i][key[j]] - i;
                } else {
                    cw = n - i + clockwise[i][key[j]];
                }
                int acw;
                if (anticlockwise[i][key[j]] <= i) {
                    acw = i - anticlockwise[i][key[j]];
                } else {
                    acw = i + n - anticlockwise[i][key[j]];
                }
                next[i] = 1 + std::min(cw + prev[clockwise[i][key[j]]], acw + prev[anticlockwise[i][key[j]]]);
            }
        }
        return next[0];
    }
};
37163