algoadvance

You are given a string word consisting of lowercase English letters. You are typing on a special typewriter that only has lowercase English letters arranged in a circle, as shown in the figure below:

a <- b <- c
|    |
v    v
z -> y -> x

Each second, you may perform one of the following operations:

The initial position of the pointer is always at character ‘a’. Return the minimum number of seconds needed to type out the entire string word.

Clarifying Questions

  1. Can word be empty?
    • No, there will always be at least one character in word.
  2. Is the circle traversal required, or can we just consider a direct distance?
    • The circular nature must be considered to compute the shortest path for each move.

Strategy

  1. Start at ‘a’ and initialize the total time counter as 0.
  2. For each character in the word:
    • Calculate the clockwise distance between the current character and the target character.
    • Calculate the counterclockwise distance between the current character and the target character.
    • The actual time to move will be the minimum of these two distances.
    • Add this move time plus one additional second for typing the character.
  3. Update the current position to the new character after each iteration.
  4. Sum up all the time taken and return it as the result.

Code

def minTimeToType(word: str) -> int:
    def get_distance(char1: str, char2: str) -> int:
        pos1 = ord(char1) - ord('a')
        pos2 = ord(char2) - ord('a')
        clockwise_distance = (pos2 - pos1) % 26
        counterclockwise_distance = (pos1 - pos2) % 26
        return min(clockwise_distance, counterclockwise_distance)

    total_time = 0
    current_char = 'a'
    
    for char in word:
        move_time = get_distance(current_char, char)
        total_time += move_time + 1  # +1 for typing the character
        current_char = char
    
    return total_time

# Example usage:
# word = "abc"
# print(minTimeToType(word))  # Output: 5

Time Complexity

The time complexity for this solution is (O(n)), where (n) is the length of the string word. This is because we are iterating over each character of the word exactly once and performing constant-time operations for each character.

Try our interview co-pilot at AlgoAdvance.com