# Freedom Trail

This page explains Java solution to problem `Freedom Trail` using `TreeMap` data structure.

## Problem Statement

In the video game Fallout `4`, the quest "Road to Freedom" requires players to reach a metal dial called the "Freedom Trail Ring", and use the dial to spell a specific keyword in order to open the door.

Given a string ring, which represents the code engraved on the outer ring and another string key, which represents the keyword needs to be spelled. You need to find the minimum number of steps in order to spell all the characters in the keyword.

Initially, the first character of the ring is aligned at `12:00` direction. You need to spell all the characters in the string key one by one by rotating the ring clockwise or anticlockwise to make each character of the string key aligned at `12:00` direction and then by pressing the center button.

At the stage of rotating the ring to spell the key character `key[i]`:

• 1. You can rotate the ring clockwise or anticlockwise one place, which counts as `1` step. The final purpose of the rotation is to align one of the string ring's characters at the `12:00` direction, where this character must equal to the character `key[i]`.
• 2. If the character `key[i]` has been aligned at the `12:00` direction, you need to press the center button to spell, which also counts as `1` step. After the pressing, you could begin to spell the next character in the key (next stage), otherwise, you've finished all the spelling.
Example 1:

Input: ring = "godding", key = "gd"
Output: 4
Explanation:
For the first key character 'g', since it is already in place, we just need 1 step to spell this character.
For the second key character 'd', we need to rotate the ring "godding" anticlockwise by two steps to make it become "ddinggo".
Also, we need 1 more step for spelling. So the final output is 4.

## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
package com.vc.hard;

import java.util.*;

class FreedomTrail {
public int findRotateSteps(String ring, String key) {
int rLength = ring.length();
int kLength = key.length();

HashMap<Character, List<Integer>> map = new HashMap<>();
for(int i = 0; i < rLength; i++) {
char ch = ring.charAt(i);
List<Integer> list = map.getOrDefault(ch, new ArrayList<>());
map.put(ch, list);
}

char firstChar = key.charAt(0);
TreeMap<Integer, Integer> prevMap = new TreeMap<>();
for(Integer index: map.getOrDefault(firstChar, new ArrayList<>())) {
prevMap.put(index, 1 + Math.min(index, rLength - index));
}

for(int i = 1; i < kLength; i++) {
char current = key.charAt(i);

TreeMap<Integer, Integer> currentMap = new TreeMap<>();
for(Integer index: map.getOrDefault(current, new ArrayList<>())) {
Integer left = prevMap.floorKey(index);
Integer right = prevMap.ceilingKey(index);

if(left == null) left = prevMap.lastKey();
if(right == null) right = prevMap.firstKey();

//Anti-clock moves
int anti = left <= index ? index - left : rLength + index - left;
anti += prevMap.get(left);

//Clockwise moves
int clock = right >= index ? right - index : rLength - index + right;
clock += prevMap.get(right);

currentMap.put(index, Math.min(anti, clock) + 1);
}
prevMap = currentMap;
}

int res = Integer.MAX_VALUE;
for(Map.Entry<Integer, Integer> entry: prevMap.entrySet()) {
res = Math.min(res, entry.getValue());
}
return res;
}
}
``````

## Time Complexity

O(MN * log M) Where
M is number of elements in an input string ring
N is number of elements in an input string key

## Space Complexity

O(M + N) Where
M is number of elements in an input string ring
N is number of elements in an input string key