LeetCode Problem 514

Difficulty: 🔴 Hard
Topics: String, Dynamic Programming, Depth-First Search, Breadth-First Search

Solution

LeetCode 514 - Freedom Trail

Problem Understanding

The problem models a circular dial, represented by the string ring, where each character is engraved at a position around the circle. Another string, key, represents the sequence of characters we must spell.

At the beginning, the character at index 0 of ring is aligned at the "12:00" position. To spell each character in key, we may rotate the ring clockwise or counterclockwise until one occurrence of the required character is aligned at "12:00". After alignment, we must press the center button, which costs one additional step.

The goal is to compute the minimum total number of steps required to spell the entire key.

The important detail is that the ring is circular. Moving from position 0 to position n - 1 costs only one step because we can rotate in either direction. For any two positions, the actual rotation cost is the minimum of:

• clockwise distance
• counterclockwise distance

The input sizes are relatively small:

• 1 <= ring.length <= 100
• 1 <= key.length <= 100

Even though these limits are not huge, a naive recursive exploration can still become extremely expensive because many characters may appear multiple times in the ring. Every duplicate character creates branching choices.

Another important observation is that the problem guarantees every character in key exists somewhere in ring. Therefore, we never need to handle impossible states.

Several edge cases are important:

• A character may appear many times in ring, and choosing the closest occurrence greedily is not always optimal.
• The ring is circular, so wrapping around must be handled correctly.
• ring and key can both have length 1.
• Consecutive identical characters in key should only require pressing the button again without rotating.

Approaches

Brute Force Approach

A brute force solution recursively tries every possible occurrence of each character in key.

Suppose the current ring pointer is at position current, and we need to spell key[i]. We can:

1. Find every index in ring where ring[index] == key[i]
2. Rotate to each candidate index
3. Recursively solve the remaining suffix of key

The recursive transition computes:

• rotation cost
• plus one button press
• plus the cost of solving the remaining characters

This approach is correct because it explores every possible sequence of rotations and therefore eventually finds the minimum total cost.

However, it is too slow without memoization. If a character appears multiple times, the recursion branches heavily. In the worst case, the number of states grows exponentially with the length of key.

Key Insight

The crucial observation is that the problem contains overlapping subproblems.

The future cost depends only on:

• the current position of the ring
• the current index in key

If we already computed the minimum cost for a state (ring_position, key_index), we should reuse it instead of recomputing it.

This naturally leads to dynamic programming.

We also preprocess the ring by storing all indices for each character. Then, instead of scanning the entire ring every time, we can directly jump to all candidate positions for a target character.

The optimal solution uses DFS with memoization:

• State: (current_ring_position, current_key_index)

• Transition:

• try every matching occurrence of key[current_key_index]

• compute rotation distance

• recursively solve the remaining substring

Because there are at most 100 * 100 = 10,000 states, the solution becomes efficient.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	O(key.length)	Explores every possible rotation sequence
Optimal DFS + Memoization	O(K × R × M)	O(K × R)	Reuses subproblem results and only explores valid character positions

Where:

• K = len(key)
• R = len(ring)
• M = average number of matching character positions

Since all constraints are at most 100, this runs comfortably within limits.

Algorithm Walkthrough

1. Create a mapping from each character to all indices where it appears in ring.

This preprocessing step is important because many characters may appear multiple times. Instead of scanning the ring repeatedly, we can instantly retrieve all candidate positions for a character. 2. Define a recursive DFS function.

The DFS state is:

• ring_pos, the current aligned position
• key_index, the next character we need to spell

The function returns the minimum number of steps needed to spell key[key_index:]. 3. Handle the base case.

If key_index == len(key), then we already spelled the entire key, so the remaining cost is 0. 4. Retrieve all candidate positions for the target character.

Let:

target = key[key_index]

Using the preprocessing map, obtain every position in ring where this character appears. 5. Compute rotation cost for each candidate.

For every candidate position:

• clockwise distance:

abs(candidate - ring_pos)

• counterclockwise distance:

ring_length - abs(candidate - ring_pos)

The actual rotation cost is the smaller of the two. 6. Recursively compute the remaining cost.

The total cost becomes:

• rotation steps
• plus one button press
• plus recursive cost for the next character

7. Take the minimum over all candidates.

Since multiple occurrences may exist, we must explore all of them to ensure optimality. 8. Memoize the result.

Store the answer for (ring_pos, key_index) so repeated states are computed only once.

Why it works

The algorithm works because every valid solution can be decomposed into smaller independent subproblems. At each stage, the only information needed for future decisions is:

• the current ring alignment
• the next key character index

The DFS explores every valid next alignment while memoization guarantees each state is solved once. Since the recurrence always considers all possible transitions and takes the minimum, the final result is globally optimal.

Python Solution

from collections import defaultdict
from functools import lru_cache
from typing import List

class Solution:
    def findRotateSteps(self, ring: str, key: str) -> int:
        char_positions = defaultdict(list)

        for index, char in enumerate(ring):
            char_positions[char].append(index)

        ring_length = len(ring)

        @lru_cache(None)
        def dfs(ring_pos: int, key_index: int) -> int:
            if key_index == len(key):
                return 0

            target_char = key[key_index]
            minimum_steps = float("inf")

            for target_pos in char_positions[target_char]:
                direct_distance = abs(target_pos - ring_pos)
                rotation_steps = min(
                    direct_distance,
                    ring_length - direct_distance
                )

                total_steps = (
                    rotation_steps
                    + 1
                    + dfs(target_pos, key_index + 1)
                )

                minimum_steps = min(minimum_steps, total_steps)

            return minimum_steps

        return dfs(0, 0)

The implementation begins by preprocessing the ring into a dictionary that maps each character to all of its indices. This allows constant time access to all candidate positions for a target character.

The recursive dfs function represents the dynamic programming state. Its parameters uniquely define the current problem:

• ring_pos is the currently aligned position
• key_index indicates which character in key must be spelled next

The @lru_cache decorator memoizes results automatically. Without memoization, many identical states would be recomputed repeatedly.

Inside the DFS, we iterate through every occurrence of the target character. For each candidate:

• compute the circular rotation distance
• add one button press
• recursively solve the remaining suffix

Finally, we return the smallest total cost among all candidates.

Go Solution

package main

import "math"

func findRotateSteps(ring string, key string) int {
	charPositions := make(map[byte][]int)

	for i := 0; i < len(ring); i++ {
		charPositions[ring[i]] = append(charPositions[ring[i]], i)
	}

	ringLength := len(ring)

	type State struct {
		ringPos  int
		keyIndex int
	}

	memo := make(map[State]int)

	var dfs func(int, int) int

	dfs = func(ringPos int, keyIndex int) int {
		if keyIndex == len(key) {
			return 0
		}

		state := State{ringPos, keyIndex}

		if value, exists := memo[state]; exists {
			return value
		}

		minimumSteps := math.MaxInt32
		targetChar := key[keyIndex]

		for _, targetPos := range charPositions[targetChar] {
			directDistance := abs(targetPos - ringPos)

			rotationSteps := min(
				directDistance,
				ringLength-directDistance,
			)

			totalSteps := rotationSteps +
				1 +
				dfs(targetPos, keyIndex+1)

			minimumSteps = min(minimumSteps, totalSteps)
		}

		memo[state] = minimumSteps
		return minimumSteps
	}

	return dfs(0, 0)
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

func min(a int, b int) int {
	if a < b {
		return a
	}
	return b
}

The Go implementation follows the same logic as the Python solution, but Go does not provide built in memoization decorators like lru_cache. Instead, we explicitly store results in a map[State]int.

A custom State struct is used as the memoization key because the DP state depends on both:

• current ring position
• current key index

Go also requires helper functions for abs and min.

Since all values are small, integer overflow is not a concern.

Worked Examples

Example 1

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

Preprocessing

Character	Positions
g	[0, 6]
o	[1]
d	[2, 3]
i	[4]
n	[5]

Ring length is 7.

Initial state:

ring_pos = 0
key_index = 0
target = 'g'

Step 1, Spell 'g'

Possible positions for 'g':

Target Position	Distance	Circular Cost
0	0	0
6	6	1

Option 1: Use position 0

rotation = 0
press = 1

Current cost:

1

Recursive state:

dfs(0, 1)

Step 2, Spell 'd'

Possible positions for 'd':

Target Position	Distance	Circular Cost
2	2	2
3	3	3

Choose position 2.

Cost:

rotation = 2
press = 1

Total:

1 + 2 + 1 = 4

Final answer:

4

Example 2

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

The algorithm repeatedly chooses optimal rotations while memoizing intermediate states.

A condensed trace:

Key Character	Best Target Position	Rotation Cost	Press Cost	Running Total
g	0	0	1	1
o	1	1	1	3
d	2	1	1	5
d	2	0	1	6
i	4	2	1	9
n	5	1	1	11
g	6	1	1	13

Final answer:

13

Complexity Analysis

Measure	Complexity	Explanation
Time	O(K × R × M)	Each DP state explores matching positions for a character
Space	O(K × R)	Memoization table stores one value per state

Where:

• K = len(key)
• R = len(ring)
• M = average occurrences of a character

In the worst case, every character appears everywhere, giving roughly O(K × R²). With maximum size 100, this is still efficient.

The space complexity comes from:

• the memoization cache
• the character position mapping
• recursion stack depth up to len(key)

Test Cases

solution = Solution()

# Provided examples
assert solution.findRotateSteps("godding", "gd") == 4  # Basic example
assert solution.findRotateSteps("godding", "godding") == 13  # Full traversal

# Single character ring and key
assert solution.findRotateSteps("a", "a") == 1  # Only button press needed

# Repeated same character in key
assert solution.findRotateSteps("abcde", "aaa") == 3  # No extra rotation after first

# Multiple duplicate characters
assert solution.findRotateSteps("ababcab", "acba") == 8  # Requires choosing optimal duplicates

# Wraparound rotation
assert solution.findRotateSteps("abcde", "ea") == 4  # Circular movement is cheaper

# Ring with all identical characters
assert solution.findRotateSteps("aaaaa", "aaa") == 3  # Always already aligned

# Frequent branching possibilities
assert solution.findRotateSteps("pqwcx", "cpqwx") == 13  # Multiple directional choices

# Consecutive duplicate letters
assert solution.findRotateSteps("abcabc", "cc") == 2  # Stay on same aligned character

# Longer repeated pattern
assert solution.findRotateSteps("iotfo", "fioot") == 11  # Tests DP reuse

# Minimum boundary
assert solution.findRotateSteps("z", "z") == 1  # Smallest valid input

Test Summary

Test	Why
"godding", "gd"	Verifies sample behavior
"godding", "godding"	Verifies longer traversal
"a", "a"	Smallest possible input
"abcde", "aaa"	Consecutive repeated key characters
"ababcab", "acba"	Multiple duplicate choices
"abcde", "ea"	Validates circular wraparound
"aaaaa", "aaa"	All characters identical
"pqwcx", "cpqwx"	Stress test for branching
"abcabc", "cc"	No movement between repeated characters
"iotfo", "fioot"	Ensures memoization effectiveness
"z", "z"	Boundary value test

Edge Cases

Multiple Occurrences of the Same Character

A naive greedy strategy might always choose the nearest occurrence of a character. This can fail because a slightly more expensive move now may create a much cheaper future configuration.

For example, if several copies of a character exist around the ring, choosing the closest one may place the pointer badly for the next required letter. The implementation handles this correctly by exploring every occurrence and taking the global minimum through dynamic programming.

Circular Wraparound

The ring is circular, so moving from index 0 to index n - 1 costs only one step. Forgetting this detail leads to incorrect distance calculations.

The implementation correctly computes:

min(distance, ring_length - distance)

This guarantees the shorter rotational direction is always used.

Consecutive Identical Characters in the Key

If the next required character is already aligned at "12:00", no rotation is necessary. Only the button press should be counted.

For example:

ring = "abc"
key = "aa"

After spelling the first 'a', the second 'a' requires only another button press.

The DFS naturally handles this because the rotation distance becomes 0.

Ring with All Identical Characters

If every character in the ring is the same, there are many equivalent positions. A poorly designed algorithm may repeatedly recompute identical states.

Memoization prevents this inefficiency by caching previously solved states.