1974. Minimum Time to Type Word Using Special Typewriter

EasyGreedyString

Problem Description

The problem describes a special typewriter with the lowercase English alphabet arranged in a circle, starting at 'a' and ending with 'z'. The pointer of the typewriter starts at 'a' and can only type the character it is pointing at. To type a given string, you can either move the pointer clockwise or counterclockwise around the circle to reach the desired character or you can type the character the pointer is currently on. Each of these operations takes one second. The task is to find the minimum amount of time required to type a given word using this typewriter.

Intuition

To minimize the time taken to type a word, we should take the shortest path to reach each character from the current position of the pointer. When we want to move from one character to another, we have two possible paths:

Moving clockwise
Moving counterclockwise

The shortest path is the one which has the least number of characters between the current and the target characters, considering the circular arrangement of the typewriter.

The intuition behind the solution is:

Calculate the difference in the positions of the current and the desired characters.
Determine whether it is quicker to reach the next character by moving clockwise or counterclockwise.
Add this minimum number of moves to an accumulator that keeps track of the total seconds needed.
Since typing the character also takes one second, we add one second for every character typed.

Thus the total time taken for typing the word will be the sum of the shortest number of moves to each character plus the number of characters in the word.

Learn more about Greedy patterns.

Solution Approach

To implement the solution, we employ a straightforward approach without the need for complex data structures or algorithms. The solution makes use of the Python ord() function, which returns the ASCII value of a character, to easily calculate the position of letters on the typewriter.

Here's a step-by-step breakdown of the Solution code:

Initialize ans as 0 to keep track of the total number of seconds taken, and prev as 0 to store the position of the previously typed character ('a', at the beginning, represented by 0).
Iterate over each character c in the given word word.
- Calculate curr which is the position of the character c by subtracting the ASCII value of 'a' from the ASCII value of c. This effectively translates the character to a numerical position in the range 0-25 on the circle.
Calculate the absolute difference t between curr (the target character's position) and prev (the current character's position). This represents the distance if we move in one direction without considering the circular nature.
Since the typewriter is circular, we also calculate the distance if we were to go the other way around the circle, which is 26 - t. Pick the minimum of these two values, which is the shortest path to the next character.
Update ans by adding the time taken to move to the next character (t) plus one second to account for the time taken to type the character (since every operation takes one second).
Set prev to curr as we have now moved to the next character.
After processing all characters in word, return ans, which now contains the minimum time to type out the given word.

This approach ensures that we always take the shortest path to the next character, thereby minimizing the overall time taken to type the entire word. It leverages the circular nature of the alphabet arrangement by always considering the direct and reverse paths and choosing the quicker one.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's take the word "bza" as an example to illustrate the solution approach.

We start with ans = 0 and prev = 0 since the typewriter pointer starts at the character 'a'.
The first character we need to type is 'b'.
- We calculate the position of 'b' by subtracting the ASCII value of 'a' from that of 'b' (ord('b') - ord('a') = 1 - 0 = 1). So curr = 1.
- The absolute difference t between curr and prev is 1 - 0 = 1.
- The other way round the circle would be 26 - 1 = 25. We take the minimum of 1 and 25 which is 1.
- We add this to ans along with 1 second for typing: ans = 0 + 1 + 1 = 2.
- We update prev to curr. So, prev = 1.
Now, the next character is 'z'.
- Its position is ord('z') - ord('a') = 25.
- The difference t is abs(25 - 1) = 24.
- Going the other way around, 26 - 24 = 2. We pick the minimum which is 2.
- Update ans to 2 + 2 + 1 = 5.
- Update prev to curr (prev = 25).
Finally, we need to type 'a', going back to the start.
- The position of 'a' is ord('a') - ord('a') = 0.
- The difference t is abs(0 - 25) = 25.
- Going the other way around, 26 - 25 = 1, which is the shorter path.
- Update ans to 5 + 1 + 1 = 7.
- Since it's the last character, we don't need to update prev.

After walking through the steps, the minimum time required for typing "bza" with our special typewriter is 7 seconds. We moved from 'a' to 'b' in 2 seconds, 'b' to 'z' in 3 seconds, and 'z' to 'a' in 2 seconds. Each move includes the time taken to type the character.

Solution Implementation

1class Solution:
2    def minTimeToType(self, word: str) -> int:
3        # Initialize the time to type the word to 0 and the initial pointer position to 'a' (which is 0 in 0-25 index)
4        total_time = pointer_position = 0
5
6        # Iterate over each character in the word
7        for char in word:
8            # Find the position of the current character (0-25 index)
9            current_position = ord(char) - ord('a')
10          
11            # Calculate the distance between the current and previous character
12            distance = abs(pointer_position - current_position)
13          
14            # The minimum rotations needed is either the direct distance or the wrap around distance
15            # Wrap around distance can be calculated by subtracting direct distance from total characters (26)
16            distance = min(distance, 26 - distance)
17          
18            # Add the distance to type the character, plus 1 second for the typing action
19            total_time += distance + 1
20          
21            # Update pointer position to the current character's position
22            pointer_position = current_position
23      
24        # Return the total time to type the word
25        return total_time
26

1class Solution {
2    // Method to calculate the minimum time to type a word given the initial pointer position is at 'a'
3    public int minTimeToType(String word) {
4        int totalTime = 0; // Total time to type the word
5        int prevPosition = 0; // Starting position is 'a', so the initial index is 0
6
7        // Iterate through each character in the word
8        for (char ch : word.toCharArray()) {
9            int currentPosition = ch - 'a'; // Convert the character to an index (0-25)
10          
11            // Calculate the clockwise and counterclockwise distance between the current and previous character
12            int clockwiseDistance = Math.abs(currentPosition - prevPosition);
13            int counterClockwiseDistance = 26 - clockwiseDistance;
14          
15            // Take the minimum distance of the two possible ways to type the character
16            int minDistanceToType = Math.min(clockwiseDistance, counterClockwiseDistance);
17          
18            // Add the distance to type the character + 1 second for typing the character itself
19            totalTime += minDistanceToType + 1;
20          
21            // Update the previous position to the current character's position for the next iteration
22            prevPosition = currentPosition;
23        }
24
25        // Return the total time to type the word
26        return totalTime;
27    }
28}
29

1class Solution {
2public:
3    // Function to calculate the minimum time to type a word on a circular keyboard
4    int minTimeToType(string word) {
5        // Initialize the answer with 0 time
6        int totalTime = 0;
7        // Starting at 'a', represented as 0
8        int previousPosition = 0;
9        // Iterate over each character in the word
10        for (char& currentChar : word) {
11            // Find the numeric position of the current character, 'a' being 0
12            int currentPosition = currentChar - 'a';
13            // Calculate the direct distance between previous and current position
14            int directDistance = abs(previousPosition - currentPosition);
15            // Calculate the circular distance (26 letters in the alphabet)
16            int circularDistance = 26 - directDistance;
17            // Take the minimum of the direct and circular distances
18            int travelTime = min(directDistance, circularDistance);
19            // Add travel time for this character plus 1 second for typing the character
20            totalTime += travelTime + 1;
21            // Set the previous position to the current character's position for the next iteration
22            previousPosition = currentPosition;
23        }
24        // Return the total time taken to type the word
25        return totalTime;
26    }
27};
28

1// Function to calculate the minimum time to type a word on a circular keyboard
2function minTimeToType(word: string): number {
3    // Initialize the total time with 0 time
4    let totalTime: number = 0;
5    // Starting at 'a', represented as 0
6    let previousPosition: number = 0;
7
8    // Iterate over each character in the word
9    for (const currentChar of word) {
10        // Find the numeric position of the current character, 'a' being 0
11        let currentPosition: number = currentChar.charCodeAt(0) - 'a'.charCodeAt(0);
12        // Calculate the direct distance between previous and current position
13        let directDistance: number = Math.abs(previousPosition - currentPosition);
14        // Calculate the circular distance (26 letters in the alphabet)
15        let circularDistance: number = 26 - directDistance;
16        // Take the minimum of the direct and circular distances
17        let travelTime: number = Math.min(directDistance, circularDistance);
18        // Add travel time for this character plus 1 second for typing the character
19        totalTime += travelTime + 1;
20        // Set the previous position to the current character's position for the next iteration
21        previousPosition = currentPosition;
22    }
23  
24    // Return the total time taken to type the word
25    return totalTime;
26}
27

Time and Space Complexity

The time complexity of the given code is O(n), where n is the length of the input string word. This is because the code iterates through each character in the string exactly once regardless of its content.

The space complexity of the code is O(1). This is due to the fact that the amount of extra space used by the algorithm does not depend on the length of the input string and is limited to a few variables that store integers, which include ans, prev, curr, and t.

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

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

dp[i] = dp[i] + 1

dp[i] = dp[i] + dp[i - 1]

dp[i] = (dp[i] + dp[j] + 1) for j in 0 to i

dp[i] = max(dp[i], dp[j] + 1) for j in 0 to i

I don’t know