⚡Flashcard Drill➔
NeetCode #759LC-514Hard2-D Dynamic Programming
← Back to All Problems

#759 · #514 · Freedom Trail(自由之路)

📌 Problem Statement & Constraints

The string ring is written around a dial with index 0 at the top, and a center button can be pressed. To spell key, rotate the ring so the needed character is at the top (one step per position, either direction) and press the button (one step). Return the minimum total steps to spell the entire key. Constraints: 1 <= ring.length, key.length <= 100, and key is spellable from ring.

💡 Core Algorithmic Approaches

  1. Let dp[pos] be the minimum steps to spell the key prefix processed so far with the ring rotated so that index pos is at the top.
  2. For the next key character, gather every ring index holding that character; each is a candidate new state.
  3. The rotation cost from a previous position prev to cur is min(|cur - prev|, n - |cur - prev|), plus 1 for the button press.
  4. The answer is the minimum over all states after the final character.

💻 Benchmark Python3 Implementation

class Solution:
    def findRotateSteps(self, ring: str, key: str) -> int:
        from collections import defaultdict
        n = len(ring)
        pos = defaultdict(list)
        for i, ch in enumerate(ring):
            pos[ch].append(i)
        dp = {0: 0}                       # current top index -> min steps
        for ch in key:
            nxt = {}
            for cur in pos[ch]:
                best = float("inf")
                for prev, cost in dp.items():
                    dist = abs(cur - prev)
                    dist = min(dist, n - dist)     # clockwise vs counter-clockwise
                    best = min(best, cost + dist + 1)
                nxt[cur] = best
            dp = nxt
        return min(dp.values())

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(k * r^2) worst case: each key character may match many ring positions, each compared against all previous positions.
💾 Space Complexity
O(r): one dictionary of position costs.

⚠️ Interview Pitfalls & Follow-ups

  • Rotating only clockwise: the dial turns both ways, so the cost is min(dist, n - dist).
  • Forgetting the button press: each matched character costs one extra step to press the center button.
  • Choosing the nearest occurrence greedily: a locally near occurrence can be globally worse, so the DP must consider every matching position.
  • Keeping a single best position per character: several ring indices may hold the same character, and each is a distinct DP state.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related 2-D Dynamic Programming Problems