class Solution {
 public:
  int findRotateSteps(string ring, string key) {
    return dfs(ring, key, 0, {}) + key.length();
  }

 private:
  // # of rotates of ring to match key[index:]
  int dfs(const string& ring, const string& key, int index,
          unordered_map<string, int>&& memo) {
    if (index == key.length())
      return 0;
    // add the index to prevent duplicate
    const string hashKey = ring + to_string(index);
    if (memo.count(hashKey))
      return memo[hashKey];

    int ans = INT_MAX;

    // for each ring[i] == key[index]
    // we rotate the ring to match ring[i] w/ key[index]
    // then recursively match newRing w/ key[index + 1:]
    for (size_t i = 0; i < ring.length(); ++i)
      if (ring[i] == key[index]) {
        const int minRotates = min(i, ring.length() - i);
        const string& newRing = ring.substr(i) + ring.substr(0, i);
        const int remainingRotates = dfs(newRing, key, index + 1, move(memo));
        ans = min(ans, minRotates + remainingRotates);
      }

    return memo[hashKey] = ans;
  }
};

class Solution {
  public int findRotateSteps(String ring, String key) {
    Map<String, Integer> memo = new HashMap<>();
    return dfs(ring, key, 0, memo) + key.length();
  }

  // # of rotates of ring to match key[index:]
  private int dfs(final String ring, final String key, int index, Map<String, Integer> memo) {
    if (index == key.length())
      return 0;
    // add the index to prevent duplicate
    final String hashKey = ring + index;
    if (memo.containsKey(hashKey))
      return memo.get(hashKey);

    int ans = Integer.MAX_VALUE;

    // for each ring[i] == key[index]
    // we rotate the ring to match ring[i] w/ key[index]
    // then recursively match newRing w/ key[index + 1:]
    for (int i = 0; i < ring.length(); ++i)
      if (ring.charAt(i) == key.charAt(index)) {
        final int minRotates = Math.min(i, ring.length() - i);
        final String newRing = ring.substring(i) + ring.substring(0, i);
        final int remainingRotates = dfs(newRing, key, index + 1, memo);
        ans = Math.min(ans, minRotates + remainingRotates);
      }

    memo.put(hashKey, ans);
    return ans;
  }
}

class Solution:
  def findRotateSteps(self, ring: str, key: str) -> int:
    # number of rotates of ring to match key[index:]
    @lru_cache(None)
    def dfs(ring: str, index: int) -> int:
      if index == len(key):
        return 0

      ans = math.inf

      # for each ring[i] == key[index]
      # we rotate the ring to match ring[i] w/ key[index]
      # then recursively match newRing w/ key[index + 1:]
      for i, r in enumerate(ring):
        if r == key[index]:
          minRotates = min(i, len(ring) - i)
          newRing = ring[i:] + ring[:i]
          remainingRotates = dfs(newRing, index + 1)
          ans = min(ans, minRotates + remainingRotates)

      return ans

    return dfs(ring, 0) + len(key)