Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1974. Minimum Time to Type Word Using Special Typewriter - Leetcode Solution

Code Implementation

class Solution:
    def minTimeToType(self, word: str) -> int:
        time = 0
        curr = 'a'
        for ch in word:
            diff = abs(ord(ch) - ord(curr))
            time += min(diff, 26 - diff) + 1
            curr = ch
        return time
      
class Solution {
public:
    int minTimeToType(string word) {
        int time = 0;
        char curr = 'a';
        for (char ch : word) {
            int diff = abs(ch - curr);
            time += min(diff, 26 - diff) + 1;
            curr = ch;
        }
        return time;
    }
};
      
class Solution {
    public int minTimeToType(String word) {
        int time = 0;
        char curr = 'a';
        for (char ch : word.toCharArray()) {
            int diff = Math.abs(ch - curr);
            time += Math.min(diff, 26 - diff) + 1;
            curr = ch;
        }
        return time;
    }
}
      
var minTimeToType = function(word) {
    let time = 0;
    let curr = 'a';
    for (let i = 0; i < word.length; i++) {
        let ch = word[i];
        let diff = Math.abs(ch.charCodeAt(0) - curr.charCodeAt(0));
        time += Math.min(diff, 26 - diff) + 1;
        curr = ch;
    }
    return time;
};

Problem Description

You are given a string word consisting only of lowercase English letters. You have a special typewriter with only one character visible at a time, arranged in a circular fashion like a ring. The typewriter starts at the letter 'a'.

At each step, you can:
  • Type the current character (takes 1 second per character)
  • Move the pointer one character clockwise or counterclockwise (takes 1 second per move)
Your task is to calculate the minimum time in seconds required to type the entire word, starting from 'a'.

Constraints:
  • 1 ≤ word.length ≤ 100
  • word contains only lowercase English letters
Note: You must move optimally (clockwise or counterclockwise) and type each character in order.

Thought Process

The first instinct might be to simulate moving the pointer to each letter by only going clockwise. However, since the alphabet is circular, sometimes it's faster to go the other direction.

For each character in word, we need to decide whether to move clockwise or counterclockwise from the current position. The key insight is that the minimum number of moves is the smaller of:
  • The direct distance between the two letters (clockwise)
  • The wrap-around distance (counterclockwise)
After moving to the desired letter, we need to type it (which always takes 1 second).

Brute force would be to simulate both directions for every move, but with the circular alphabet of size 26, we can always compute the minimum directly.

Solution Approach

To solve the problem efficiently, we follow these steps:
  1. Start at the letter 'a' (the initial pointer position).
  2. For each character in word:
    • Calculate the absolute difference between the current pointer and the target letter. This gives the clockwise distance.
    • Calculate the counterclockwise distance as 26 - clockwise distance.
    • The minimum of these two is the optimal move to reach the target letter.
    • Add 1 second for typing the letter.
    • Update the current pointer to the new letter.
  3. Repeat until all letters are typed.
  4. Return the total time accumulated.
Why this works: By always choosing the shorter path (clockwise or counterclockwise), we guarantee the minimal movement. Using character codes (e.g., ord() in Python) makes it easy to compute distances.

Example Walkthrough

Let's use the input word = "bza":
  1. Start at 'a' (pointer at 'a').
  2. First letter is 'b':
    • Distance: |ord('b') - ord('a')| = 1
    • Counterclockwise: 26 - 1 = 25
    • Minimum is 1 move, plus 1 to type: 2 seconds
  3. Next letter is 'z' (pointer at 'b'):
    • Distance: |ord('z') - ord('b')| = 24
    • Counterclockwise: 26 - 24 = 2
    • Minimum is 2 moves, plus 1 to type: 3 seconds
  4. Next letter is 'a' (pointer at 'z'):
    • Distance: |ord('a') - ord('z')| = 25
    • Counterclockwise: 26 - 25 = 1
    • Minimum is 1 move, plus 1 to type: 2 seconds
Total time: 2 (to 'b') + 3 (to 'z') + 2 (to 'a') = 7 seconds

Time and Space Complexity

  • Brute-force approach: If we tried all possible paths, complexity would be exponential (not feasible).
  • Optimized approach (as above):
    • Time complexity: O(N), where N is the length of word, since we process each letter once.
    • Space complexity: O(1), as we only use a few variables regardless of input size.
This is efficient and suitable for the input constraints.

Summary

The solution leverages the circular nature of the alphabet and always chooses the minimal movement (clockwise or counterclockwise) between letters. By calculating the shortest distance for each step and adding the typing time, we ensure an optimal solution in linear time. The key insight is to use character code arithmetic to handle the wrapping efficiently, making the solution both elegant and performant.