Hard

Quiz

#514 Freedom Trail

APPROACH

You have a circular dial engraved with the string ring. To unlock a door you must spell out every character in the string key by rotating the dial so the matching character reaches the top position, then pressing a confirm button.

The dial starts with its first character at the top. Each single-position rotation (clockwise or counterclockwise) costs one step, and each button press also costs one step. Return the minimum total steps required to spell all characters in key.

At each stage, to spell key[i]:

- Rotate the dial one position clockwise or counterclockwise (one step each) until a character equal to key[i] is at the top.

- Press the confirm button (one step) to record the character, then move on to key[i+1].

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.

Example 2:

Input: ring = "godding", key = "godding"

Output: 13

1 of 4

1:00

What is the optimal approach for this problem?