class Solution {
    public int findRotateSteps(String ring, String key) {
        // Map: (ringIndex, keyIndex) -> steps
        Map<MemoKey, Integer> memo = new HashMap<>();
        return helper(ring, key, 0, 0, memo);
    }

    // ringIndex: specifies which index of ring is at 12:00.
    // keyIndex: specifies the index of the next letter we need.
    public int helper(String ring, String key, int ringIndex, int keyIndex,
                     Map<MemoKey, Integer> memo) {
        if (keyIndex == key.length()) {
            return 0;
        }

        MemoKey memoKey = new MemoKey(ringIndex, keyIndex);
        if (memo.containsKey(memoKey)) {
            return memo.get(memoKey);
        }

        char nextChar =  key.charAt(keyIndex);

        // Find two indices of nextChar that are closest to us.
        int nextLeft = getNextLeft(ring, ringIndex, nextChar);
        int nextRight = getNextRight(ring, ringIndex, nextChar);

        // Find how many steps to get to nextLeft and nextRight.
        int stepsLeft = getStepsLeft(ringIndex, nextLeft, ring.length());
        int stepsRight = getStepsRight(ringIndex, nextRight, ring.length());


        //System.out.printf("Going from %d to %s left (idx %d). %d steps.\n",
        //                 ringIndex, nextChar, nextLeft, stepsLeft);


        // Recurse going left and right and return the min.
        int futureStepsLeft = helper(ring, key, nextLeft, keyIndex + 1, memo);
        int futureStepsRight = helper(ring, key, nextRight, keyIndex + 1, memo);

        // Return the min of going left or right.
        // Add 1 because spelling a letter takes a step.
        int totalStepsLeft = stepsLeft + futureStepsLeft;
        int totalStepsRight = stepsRight + futureStepsRight;

        int result = 1 + Math.min(totalStepsLeft, totalStepsRight);
        memo.put(memoKey, result);
        return result;
    }

    private static class MemoKey  {
        private int ringIdx;
        private int keyIdx;

        MemoKey(int ringIdx, int keyIdx)  {
            this.ringIdx = ringIdx;
            this.keyIdx = keyIdx;
        }

        @Override
        public int hashCode() {
            return Objects.hash(ringIdx, keyIdx);
        }

        @Override
        public boolean equals(Object other) {
            if (other instanceof MemoKey) {
                MemoKey otherMK = (MemoKey) other;
                return this.ringIdx == otherMK.ringIdx
                    && this.keyIdx == otherMK.keyIdx;
            }
            return false;
        }
    }

    private int getNextLeft(String ring, int ringIndex, char nextChar) {
        return getNext(ring, ringIndex, nextChar, -1);
    }

    private int getNextRight(String ring, int ringIndex, char nextChar) {
        return getNext(ring, ringIndex, nextChar, 1);
    }

    private int getNext(String ring, int ringIndex, char nextChar, int increment) {
        int curr = ringIndex;
        while (ring.charAt(curr) != nextChar) {
            curr = (curr + increment + ring.length()) % ring.length();
        }
        return curr;
    }

    private int getStepsLeft(int ringIndex, int nextLeft, int ringLen) {
        if (nextLeft <= ringIndex) {
            return ringIndex - nextLeft;
        }
        return ringIndex + ringLen - nextLeft;
    }

    private int getStepsRight(int ringIndex, int nextRight, int ringLen) {
        if (nextRight >= ringIndex) {
            return nextRight - ringIndex;
        }
        return nextRight + ringLen - ringIndex;
    }


}