Minimum Time to Type Word Using Special Typewriter

Difficulty: Easy | Acceptance: 78.70% | Paid: No Topics: String, Greedy

There is a special typewriter with lowercase English letters ‘a’ to ‘z’ arranged in a circle with a pointer. Initially, the pointer points to ‘a’. The typewriter can perform two operations in one second:

1. Move the pointer one character counterclockwise or clockwise.
2. Type the character the pointer is currently on.

Given a string word, return the minimum number of seconds to type it.

Table of Contents

• Examples
• Constraints
• Greedy Simulation
• Functional Approach

Examples

Example 1

Input: word = "abc"
Output: 5
Explanation:
The pointer is initially at 'a'.
- Type 'a': 1 second.
- Move pointer to 'b': 1 second.
- Type 'b': 1 second.
- Move pointer to 'c': 1 second.
- Type 'c': 1 second.
Total time = 1 + 1 + 1 + 1 + 1 = 5 seconds.

Example 2

Input: word = "bza"
Output: 7
Explanation:
The pointer is initially at 'a'.
- Move pointer to 'b': 1 second.
- Type 'b': 1 second.
- Move pointer to 'z': 2 seconds (counter-clockwise: b -> a -> z).
- Type 'z': 1 second.
- Move pointer to 'a': 1 second.
- Type 'a': 1 second.
Total time = 1 + 1 + 2 + 1 + 1 + 1 = 7 seconds.

Example 3

Input: word = "zjpc"
Output: 34
Explanation:
The pointer moves and types according to the minimum distance logic.
Total time sums up to 34 seconds.

Constraints

1 <= word.length <= 100
word consists of lowercase English letters.

Greedy Simulation

Intuition Since the pointer moves on a circular track of 26 letters, the shortest distance between any two characters is the minimum of the clockwise distance and the counter-clockwise distance. We can iterate through the word, calculating this minimum distance for each transition from the current character to the next.

Steps

• Initialize time to 0 and current to ‘a’.
• Iterate through each character target in word.
• Calculate the absolute difference between the positions of current and target.
• The minimum move cost is min(diff, 26 - diff).
• Add this move cost plus 1 (for typing) to time.
• Update current to target.

class Solution:
    def minTimeToType(self, word: str) -> int:
        time = 0
        current = 'a'
        
        for target in word:
            diff = abs(ord(target) - ord(current))
            time += min(diff, 26 - diff) + 1
            current = target
            
        return time

Complexity

• Time: O(n), where n is the length of the word. We iterate through the string once.
• Space: O(1), we only use a few variables for tracking state.
• Notes: This is the most optimal approach as it requires a single pass.

Functional Approach

Intuition We can view the problem as a reduction where we accumulate the total time based on the transition between consecutive characters. This approach leverages functional programming constructs like reduce to handle the accumulation implicitly.

Steps

• Define a helper function to calculate the distance between two characters.
• Use a reduce function on the word string.
• The accumulator holds the total time and the previous character.
• For each character, calculate the transition cost and update the accumulator.

class Solution:
    def minTimeToType(self, word: str) -> int:
        def get_time(acc, char):
            total, prev = acc
            diff = abs(ord(char) - ord(prev))
            move = min(diff, 26 - diff)
            return (total + move + 1, char)
        
        final_time, _ = reduce(get_time, word, (0, 'a'))
        return final_time

Complexity

• Time: O(n), where n is the length of the word.
• Space: O(1), constant space used for accumulation.
• Notes: While functionally elegant, it offers no performance benefit over the iterative approach and may be slightly less readable to those unfamiliar with functional patterns.