Freedom Trail

HardDynamic Programming2d dp

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

A circular dial shows the string ring, one character per slot. Slot 0 starts aligned with a marker at the 12 o'clock position. You must spell key one character at a time. To spell a character, rotate the ring clockwise or counterclockwise one slot per step until any slot holding that character is at 12 o'clock, then press the center button (1 more step). Rotation distance between slots i and j is the shorter way around the circle. The ring stays where you left it for the next character. Return the minimum total number of steps (rotations plus button presses) to spell all of key. Every character of key is guaranteed to appear in ring.

Examples

Input: ring = "godding", key = "gd"
Output: 4
Press at "g" (1 step), rotate 2 steps to the "d" at slot 2, press (1 step): 1 + 2 + 1 = 4.
Input: ring = "godding", key = "godding"
Output: 13
7 button presses plus 6 rotation steps in the best plan.

Constraints

  • 1 <= ring.length, key.length <= 100
  • `ring` and `key` consist of lowercase English letters
  • Every character of `key` appears in `ring`

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More 2d dp problems