Minimum Time To Type Word Using Special Typewriter - Leetcode Solution

The problem statement for Minimum Time To Type Word Using Special Typewriter on LeetCode is as follows:

You have a special typewriter that can type one character at a time. Initially, the typewriter is at the position ‘A’. In one step, you can move the typewriter one step to the left or to the right. In addition, you can change the character being typed to any other character in the English alphabet.

Given a string word, return the minimum number of steps to type out the word using the special typewriter.

To solve this problem, we need to analyze the given constraints and devise an approach that can solve the problem efficiently. Here’s a detailed solution of the problem explaining the approach and the steps involved:

Algorithm:

1. First, we initialize a variable ‘ans’ to store the minimum number of steps required to type the given word.

2. Then, we loop through the characters of the given word and calculate the difference between the ASCII value of the current character and the ASCII value of the previous character.

3. If the difference is less than or equal to 13, we add the difference to the variable ‘ans’. This is because we can move the typewriter left or right to reach the next character in a minimum number of steps if the difference between the current character and the previous character is less than or equal to 13.

4. Otherwise, we add the difference between 26 and the difference to the variable ‘ans’. This is because we can reach the next character in a minimum number of steps by moving the typewriter in the opposite direction (left or right) and then changing the character to the next one.

5. Finally, we add the length of the given word to the variable ‘ans’ to consider the steps required to type the last character.

6. Return the value of ‘ans’.

Pseudo Code:

Let word be the given string

ans = 0 prev = 'A'

for i in range(len(word)): diff = abs(ord(word[i]) - ord(prev)) if diff <= 13: ans += diff else: ans += 26 - diff prev = word[i]

ans += len(word)

return ans

Time Complexity: O(n) where 'n' is the length of the given word. This is because we are looping through the characters of the given word only once.

Space Complexity: O(1) as we are not using any extra space except for the variables used in the algorithm.

1