We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Freedom Trail

Number: 514

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Given a circular dial (represented as a string "ring") and a keyword (represented as a string "key"), the goal is to determine the minimum number of steps needed to spell out the keyword. Each step can either be a rotation (clockwise or anticlockwise by one position) or pressing a button when the correct character is aligned at the "12:00" position. Initially, the first character of the ring is at the "12:00" position. The challenge lies in calculating the optimal rotation sequence to minimize the total number of steps.

Key Insights

  • Use dynamic programming with memoization or DFS since decisions at one step affect future rotations.
  • Precompute and store the indices of each character occurring in the ring for quick lookup during transitions.
  • Rotation distance between two indices on a circular ring is computed as: min(|i - j|, len(ring) - |i - j|).
  • The DP state can be represented by the current index in the key and the current aligned position in the ring.

Space and Time Complexity

Time Complexity: O(m * n) in the worst-case, where m is the length of key and n is the length of ring, because every state (key index, ring position) is computed once. Space Complexity: O(m * n) for the memoization and recursion stack space.

Solution

The approach is to use a DFS with memoization (or a bottom-up DP) where each state is defined by the current character index in the key and the current position in the ring. For each state, iterate through all positions in the ring that match the current key character, compute the cost of rotation to that position (using the minimum distance on the circle), add one step for pressing the button, and then recursively solve for the next character in the key. The memoization avoids repeated calculations for the same state.

Code Solutions

# Python Solution

from functools import lru_cache

def findRotateSteps(ring, key):
    n = len(ring)
    # Build a mapping of characters to their positions in the ring
    char_to_indices = {}
    for i, ch in enumerate(ring):
        if ch not in char_to_indices:
            char_to_indices[ch] = []
        char_to_indices[ch].append(i)
    
    # DFS with memoization: state is (key_index, current_ring_pos)
    @lru_cache(maxsize=None)
    def dfs(key_index, current_pos):
        # If all key characters are processed, no more steps needed
        if key_index == len(key):
            return 0
        min_steps = float('inf')
        # For every occurrence of the required character in the ring
        for pos in char_to_indices[key[key_index]]:
            # Calculate the distance between current position and new position on the circular ring
            distance = abs(pos - current_pos)
            rotation_steps = min(distance, n - distance)
            # 1 step for pressing the button after rotation
            steps = rotation_steps + 1 + dfs(key_index + 1, pos)
            min_steps = min(min_steps, steps)
        return min_steps

    return dfs(0, 0)

# Example Usage:
# print(findRotateSteps("godding", "gd"))  # Expected output: 4
← Back to All Questions