Problem Description

You have a special typewriter with lowercase English letters 'a' to 'z' arranged in a circle. The typewriter has a pointer that starts at the letter 'a'.

To type a word, you can perform these operations, each taking exactly 1 second:

• Move the pointer one position clockwise or counterclockwise on the circle
• Type the character that the pointer is currently pointing to

Since the letters are arranged in a circle, you can move from 'z' to 'a' (or vice versa) in just 1 second.

Given a string word, find the minimum number of seconds needed to type out all the characters in the word.

For example, if you need to type "bza":

1. Start at 'a'
2. Move to 'b' (1 second to move clockwise) and type 'b' (1 second to type) = 2 seconds
3. From 'b', move to 'z' (2 seconds counterclockwise is faster than 24 clockwise) and type 'z' (1 second) = 3 seconds
4. From 'z', move to 'a' (1 second clockwise) and type 'a' (1 second) = 2 seconds
5. Total: 2 + 3 + 2 = 7 seconds

The key insight is that when moving between two letters, you should always choose the shorter path around the circle. If the direct distance is d, then the minimum distance is min(d, 26 - d).

Intuition

Since we need to type each character in the word, we must spend at least 1 second per character just for the typing action itself. This gives us a baseline of len(word) seconds.

The optimization opportunity lies in minimizing the movement time between characters. When moving from one letter to another on a circular arrangement, we have two choices: go clockwise or counterclockwise.

For any two letters, if we calculate their positions as numbers (where 'a' = 0, 'b' = 1, ..., 'z' = 25), the direct distance between them is |position1 - position2|. However, since the letters form a circle, we can also go "the other way around" which would take 26 - direct_distance steps.

For example, moving from 'a' to 'z':

• Clockwise: 25 steps ('a' → 'b' → ... → 'z')
• Counterclockwise: 1 step ('a' → 'z' directly, going backwards)

The greedy approach works here because each character must be typed in order, and the decision of which path to take between consecutive characters is independent - choosing the shortest path for each transition will always give the optimal total time.

Therefore, for each character in the word:

1. Calculate the direct distance from the current position
2. Compare it with going the opposite way around the circle (26 - direct_distance)
3. Choose the minimum and add it to our total time
4. Update our current position and continue

This leads to the formula: total_time = len(word) + sum of minimum distances between consecutive characters.

Learn more about Greedy patterns.

Solution Approach

The implementation follows a greedy strategy to minimize the total time:

1. Initialize the answer: Start with ans = len(word) since we need at least 1 second to type each character.

2. Track current position: Use variable a to track the ASCII value of the current position, initially set to ord("a") (the ASCII value of 'a').

3. Process each character: Convert each character in the word to its ASCII value using map(ord, word). For each character c:

   • Calculate the direct distance: d = abs(c - a)
   • Find the minimum path: min(d, 26 - d)
     • If d ≤ 13, going directly is optimal
     • If d > 13, going the opposite way around (26 - d steps) is shorter
   • Add this minimum distance to ans
   • Update the current position: a = c

4. Return the result: The final ans contains the total minimum time.

Example walkthrough with word = "bza":

• Start: ans = 3 (length of word), a = ord('a') = 97
• Character 'b' (ASCII 98):
  • d = |98 - 97| = 1
  • min(1, 26 - 1) = 1
  • ans = 3 + 1 = 4
  • Update: a = 98
• Character 'z' (ASCII 122):
  • d = |122 - 98| = 24
  • min(24, 26 - 24) = min(24, 2) = 2
  • ans = 4 + 2 = 6
  • Update: a = 122
• Character 'a' (ASCII 97):
  • d = |97 - 122| = 25
  • min(25, 26 - 25) = min(25, 1) = 1
  • ans = 6 + 1 = 7

The algorithm runs in O(n) time where n is the length of the word, with O(1) space complexity.

Example Walkthrough

Let's trace through the solution with the word "cab":

Initial Setup:

• We need 3 seconds minimum just to type the 3 characters
• Start at position 'a' (ASCII value 97)
• Total time = 3 (for typing)

Step 1: Move from 'a' to 'c' and type 'c'

• Target: 'c' (ASCII value 99)
• Direct distance: |99 - 97| = 2
• Alternative path around circle: 26 - 2 = 24
• Choose minimum: min(2, 24) = 2
• Add 2 seconds for movement
• Total time = 3 + 2 = 5
• Current position: 'c'

Step 2: Move from 'c' to 'a' and type 'a'

• Target: 'a' (ASCII value 97)
• Direct distance: |97 - 99| = 2
• Alternative path around circle: 26 - 2 = 24
• Choose minimum: min(2, 24) = 2
• Add 2 seconds for movement
• Total time = 5 + 2 = 7
• Current position: 'a'

Step 3: Move from 'a' to 'b' and type 'b'

• Target: 'b' (ASCII value 98)
• Direct distance: |98 - 97| = 1
• Alternative path around circle: 26 - 1 = 25
• Choose minimum: min(1, 25) = 1
• Add 1 second for movement
• Total time = 7 + 1 = 8
• Current position: 'b'

Final Answer: 8 seconds

The breakdown is:

• 3 seconds for typing the 3 characters
• 2 seconds to move from 'a' to 'c'
• 2 seconds to move from 'c' to 'a'
• 1 second to move from 'a' to 'b'

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the string word. This is because the algorithm iterates through each character in the word exactly once using the for loop. Inside the loop, all operations (calculating the absolute difference, finding the minimum, and updating variables) are constant time O(1) operations.

The space complexity is O(1). The algorithm only uses a fixed amount of extra space regardless of the input size. The variables ans (to store the result), a (to track the current position), c (loop variable for each character's ASCII value), and d (to store the distance) all require constant space. The map(ord, word) creates an iterator rather than storing all values at once, so it doesn't consume additional space proportional to the input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting the Circular Nature of the Keyboard

A common mistake is calculating only the direct distance between characters without considering the wrap-around path. For example, moving from 'a' to 'z' would be calculated as 25 steps instead of the optimal 1 step going counterclockwise.

Incorrect approach:

# Wrong - only considers direct distance
distance = abs(char_position - current_position)
total_time += distance

Correct approach:

# Right - considers both direct and wrap-around distances
direct_distance = abs(char_position - current_position)
wrap_distance = 26 - direct_distance
total_time += min(direct_distance, wrap_distance)

2. Not Including Typing Time

Another pitfall is forgetting that typing each character also takes 1 second, not just the movement. Some might only count the movement time between characters.

Incorrect approach:

# Wrong - only counts movement time
total_time = 0
for char in word:
    total_time += min(direct_distance, wrap_distance)

Correct approach:

# Right - includes both movement and typing time
total_time = len(word)  # Start with typing time for all characters
for char in word:
    total_time += min(direct_distance, wrap_distance)

3. Using Character Values Instead of ASCII

Attempting to perform arithmetic operations directly on characters instead of their ASCII values will cause errors.

Incorrect approach:

# Wrong - can't subtract characters directly
distance = abs(char - current_position)

Correct approach:

# Right - convert to ASCII values first
char_position = ord(char)
distance = abs(char_position - current_position)

4. Off-by-One Error in Wrap Distance

Some might incorrectly calculate the wrap-around distance as 25 - direct_distance or 27 - direct_distance instead of 26 - direct_distance.

Why 26 is correct:

• The alphabet has 26 letters forming a circle
• If direct distance is d, going the opposite way takes exactly (26 - d) steps
• Example: From 'a' to 'c' is 2 steps forward or 24 steps backward (2 + 24 = 26)