Freedom Trail - Practice Coding Problems

Freedom Trail - Problem

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 to open the door.

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

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

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

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

Input & Output

Example 1 — Basic Case

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

› Output: 4

💡 Note: Start at 'g'(0), press button (1 step). Rotate to 'd'(2): min(2 clockwise, 5 anticlockwise) = 2 steps. Press button (1 step). Total: 1 + 2 + 1 = 4 steps.

Example 2 — Single Character

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

› Output: 1

💡 Note: Already at 'g'(0), just press button. Total: 1 step.

Example 3 — Multiple Choices

$ Input: ring = "abcde", key = "ae"

› Output: 3

💡 Note: Start at 'a'(0), press button (1 step). Rotate to 'e'(4): min(4 clockwise, 1 anticlockwise) = 1 step. Press button (1 step). Total: 1 + 1 + 1 = 3 steps.

Constraints

1 ≤ ring.length, key.length ≤ 100
ring and key consist of only lower case English letters
It's guaranteed that all characters in key exist in ring

Visualization

Tap to expand

Understanding the Visualization

Input Setup

Ring "godding" with characters at positions 0-6, key "gd" to spell

Rotation Strategy

Calculate clockwise vs anticlockwise distances, choose minimum

Optimal Path

Start at g(0), rotate to d(2), total 4 steps including button presses

Key Takeaway

🎯 Key Insight: When characters appear multiple times in the ring, use dynamic programming to find the optimal sequence of positions that minimizes total rotation steps.

Asked in

G Google 15 M Microsoft 12 a Amazon 8 f Facebook 6

The key insight is that each character in the key can appear at multiple positions in the ring, and we must choose the position that minimizes total rotation steps. The optimal approach uses Dynamic Programming with a 2D table where dp[i][j] represents minimum steps to spell first i characters ending at ring position j. Time: O(n×m²), Space: O(n×m).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force DFS	O(k^n)	O(n)	Recursively try all possible positions for each character
Dynamic Programming	O(n * m²)	O(n * m)	Bottom-up DP to find minimum steps for each state
Memoized DFS	O(n * m * k)	O(n * m)	Cache DFS results to avoid redundant calculations

Brute Force DFS — Algorithm Steps

Step 1: For each character in key, find all its positions in ring
Step 2: Use DFS to try each possible position
Step 3: Calculate rotation distance and recurse for next character
Step 4: Return minimum steps across all possibilities

Visualization

Tap to expand

Step-by-Step Walkthrough

Start Position

Begin at ring[0], need to spell key[0]

Find Targets

Find all positions where key[0] appears in ring

Try Each Path

Recursively try each position and calculate minimum steps

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <limits.h>

int min(int a, int b) {
    return a < b ? a : b;
}

int dfs(char* ring, char* key, int ringPos, int keyPos, int ringLen, int keyLen) {
    if (keyPos == keyLen) {
        return 0;
    }
    
    char targetChar = key[keyPos];
    int minSteps = INT_MAX;
    
    // Find all positions of target character in ring
    for (int i = 0; i < ringLen; i++) {
        if (ring[i] == targetChar) {
            // Calculate clockwise distance
            int clockwise = (i - ringPos + ringLen) % ringLen;
            // Calculate anticlockwise distance
            int anticlockwise = (ringPos - i + ringLen) % ringLen;
            // Choose minimum rotation + 1 for button press
            int rotationSteps = min(clockwise, anticlockwise) + 1;
            // Recursively calculate remaining steps
            int remainingSteps = dfs(ring, key, i, keyPos + 1, ringLen, keyLen);
            minSteps = min(minSteps, rotationSteps + remainingSteps);
        }
    }
    
    return minSteps;
}

int solution(char* ring, char* key) {
    return dfs(ring, key, 0, 0, strlen(ring), strlen(key));
}

int main() {
    char ring[101], key[101];
    fgets(ring, sizeof(ring), stdin);
    fgets(key, sizeof(key), stdin);
    ring[strcspn(ring, "\n")] = 0;
    key[strcspn(key, "\n")] = 0;
    
    int result = solution(ring, key);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k^n)

For each of n key characters, we try up to k ring positions, leading to exponential combinations

✓ Linear Growth

Space Complexity

O(n)

Recursion stack depth equals the length of key string

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force DFS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler