Leetcode 1974. Minimum Time to Type Word Using Special Typewriter

Problem

You have a special circular keyboard with all 26 lowercase English letters arranged in a circle. The letters are ordered from 'a' to 'z' in clockwise order, and after 'z' comes 'a' again (forming a circle).

A pointer initially points to the letter 'a'. To type a word on this keyboard, you need to:

1. Move the pointer to each required letter (you can move clockwise or counterclockwise)
2. Press the key to type that letter

Each operation takes exactly 1 second:

• Moving the pointer one position (clockwise or counterclockwise) takes 1 second
• Typing a letter (pressing the key) takes 1 second

Given a string word consisting of lowercase English letters, calculate the minimum number of seconds needed to type the entire word.

Requirements

1. Start with the pointer at letter 'a'
2. For each letter in the word, move the pointer optimally (shortest path) to that letter
3. After moving to each letter, type it (add 1 second for typing)
4. Return the total time in seconds

Constraints

• 1 ≤ word.length ≤ 100
• word consists of lowercase English letters only
• You must choose the shorter path (clockwise or counterclockwise) for each movement
• Time complexity should be O(n) where n is the length of the word
• Space complexity should be O(1)

Examples

Example 1:

` Input: word = "abc" Output: 5 Explanation:

• Start at 'a': 0 seconds to move, 1 second to type → 1 second total
• Move to 'b': 1 second to move, 1 second to type → 2 seconds
• Move to 'c': 1 second to move, 1 second to type → 2 seconds Total: 1 + 2 + 2 = 5 seconds `

Example 2:

` Input: word = "bza" Output: 7 Explanation:

• Start at 'a', move to 'b': 1 forward (1s move + 1s type) = 2s
• Move from 'b' to 'z': Going backward 2 steps is shorter than forward 24 steps (2s move + 1s type) = 3s
• Move from 'z' to 'a': 1 forward (1s move + 1s type) = 2s Total: 2 + 3 + 2 = 7 seconds `

Example 3:

` Input: word = "z" Output: 2 Explanation:

• Start at 'a', move to 'z': Going backward 1 step is shorter than forward 25 steps (1s move + 1s type) = 2s `

Hint 1: Distance Calculation For a circular arrangement of 26 letters, think about how to calculate the shortest distance between any two letters. If you're at position i and need to reach position j, you can go clockwise or counterclockwise. The shortest distance is the minimum of these two paths.

Hint 2: Formula for Circular Distance Given two positions on a circle with 26 positions, the clockwise distance is abs(target - current), and the counterclockwise distance is 26 - abs(target - current). The minimum of these two values gives you the shortest path.

Hint 3: Track Current Position You don't need to simulate the actual movement. Just keep track of your current position (starting at 'a' or position 0), calculate the minimum distance to the next character, add 1 for typing, and update your current position.

Full Solution ` def minTimeToType(word: str) -> int: # Start at position 'a' (position 0) current_pos = 0 total_time = 0

for char in word:
    # Convert character to position (0-25)
    target_pos = ord(char) - ord('a')
    
    # Calculate the direct distance (could be clockwise or counterclockwise)
    direct_distance = abs(target_pos - current_pos)
    
    # Calculate the wrap-around distance (going the other way around the circle)
    wrap_distance = 26 - direct_distance
    
    # Take the minimum of the two possible paths
    min_distance = min(direct_distance, wrap_distance)
    
    # Add movement time + typing time (1 second)
    total_time += min_distance + 1
    
    # Update current position
    current_pos = target_pos

return total_time

`

Explanation:

The solution works by:

1. Tracking Position: We maintain current_pos starting at 0 (letter 'a')

2. Converting Characters: For each character in the word, we convert it to a numerical position (0-25) using ord(char) - ord('a')

3. Finding Shortest Path: On a circular keyboard with 26 positions:

   • The direct distance is abs(target_pos - current_pos)
   • The wrap-around distance (going the opposite direction) is 26 - direct_distance
   • We take the minimum of these two values

4. Accumulating Time: For each character, we add:

   • The minimum movement distance
   • Plus 1 second for typing

5. Updating Position: After processing each character, we update our current position

Time Complexity: O(n) where n is the length of the word. We iterate through each character once.

Space Complexity: O(1) as we only use a constant amount of extra space for variables.