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

Minimum Time to Type Word Using Special Typewriter

Number: 2088

Difficulty: Easy

Paid? No

Companies: IBM, Microsoft, LinkedIn, Thomson Reuters

Problem Description

A special typewriter has the lowercase English letters 'a' to 'z' arranged in a circle with a pointer initially at 'a'. At each second, you can either move the pointer one step clockwise or counterclockwise, or type the character at the current pointer position. Given a string word, determine the minimum number of seconds required to type it.

Key Insights

  • The circle has 26 letters, so moving between letters can be done in either clockwise or counterclockwise direction.
  • For any two characters, the minimum steps required is min(|pos2-pos1|, 26 - |pos2-pos1|).
  • Typing each character always takes 1 second in addition to moving time.
  • The problem can be solved by simulating the pointer movement from the starting character 'a' through each character in the word.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the word. Space Complexity: O(1).

Solution

We simulate the pointer moving on the circular typewriter. Start with the pointer at 'a'. For each character in the word, calculate the absolute difference between the current pointer position and the target character. Since the typewriter is circular, the effective distance is the minimum of the absolute difference and 26 minus that difference. Add this movement cost and 1 second for typing the character. Update the pointer and repeat until the word is fully typed.

Code Solutions

# Define the function to compute minimum typing time for the given word.
def minTimeToType(word: str) -> int:
    # Initialize total seconds and pointer position (starting with 'a' index 0)
    total_time = 0
    current_pos = 0  # 'a' is index 0
    for char in word:
        target_pos = ord(char) - ord('a')  # Convert char to its corresponding index (0-25)
        # Calculate absolute difference between current and target positions
        diff = abs(target_pos - current_pos)
        # Calculate minimum steps in a circular array
        steps = min(diff, 26 - diff)
        # Add the movement steps and 1 second for typing the character
        total_time += steps + 1
        # Update the current pointer to target position
        current_pos = target_pos
    return total_time

# Example usage:
print(minTimeToType("abc"))  # Expected output: 5
← Back to All Questions