Greedy

Minimum Time to Type Word Using Special Typewriter

Problem Description

There is a special typewriter with lowercase English letters 'a' to 'z' arranged in a circle with a pointer. A character can only be typed if the pointer is pointing to that character. The pointer is initially pointing to the character 'a'.

Each second, you may perform one of the following operations:
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 out the characters in word.

Example

Input: word = "abc"
Output: 5
Explanation: The characters are printed as follows:
- Type the character 'a' in 1 second since the pointer is initially on 'a'.
- Move the pointer clockwise to 'b' in 1 second.
- Type the character 'b' in 1 second.
- Move the pointer clockwise to 'c' in 1 second.
- Type the character 'c' in 1 second.

Input: word = "bza"
Output: 7
Explanation: The characters are printed as follows:
- Move the pointer clockwise to 'b' in 1 second.
- Type the character 'b' in 1 second.
- Move the pointer counterclockwise to 'z' in 2 seconds.
- Type the character 'z' in 1 second.
- Move the pointer clockwise to 'a' in 1 second.
- Type the character 'a' in 1 second.

Constraints

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

💡

Try it Yourself First

When solving problems where we aim to maximize or minimize results, it's key to make the best possible choice at every step—this approach is known as the "Greedy Technique." In this problem, we're in a similar situation, where choosing the optimal option at each point can lead to the best solution. Let's dive into thinking of a greedy approach for this!

Optimal Approach

Intuition

Since the letters are arranged in a circle, when you reach the end (i.e., from 'z'), you can move directly back to 'a' and vice versa. So, if you're moving clockwise, from 'a' to 'b' would take 1 second, but from 'a' to 'z' would take 1 second as well because of the circular arrangement. Similarly, moving counterclockwise works the same way: moving from 'a' to 'z' would take 1 second, but moving from 'a' to 'b' would take 25 seconds if you go backward.

For each character in the word, you can decide whether to move clockwise or counterclockwise, depending on which direction takes the least time. This approach is based on the greedy strategy, where at each step, we choose the optimal option (the direction that takes the least time) in order to minimize the total time spent. The idea is to make the best possible decision at every character, without worrying about future steps, because each decision aims to reduce the total time as much as possible.

Example

Let’s break it down with an example to better understand how to minimize the typing time. Suppose the word you want to type is "learn".

Now, let’s move to the next character, 'l'. You have two options:

Move the pointer clockwise from 'a' to 'l'. Since the alphabet is arranged in a circle, you count the steps forward: a → b → c → ... → l. This would take 11 steps, so it takes 11 seconds.
Move the pointer counterclockwise from 'a' to 'l'. This would involve going backward through the alphabet: a → z → y → ... → m → l. This would take 15 steps, so it takes 15 seconds.

Clearly, moving clockwise is faster, so you choose that. Now, the pointer is on 'l', and typing 'l' takes 1 second.

Next, let’s move to the character 'e'. From 'l', you have two choices again:

Move the pointer clockwise from 'l' to 'e', which would involve counting the steps: l → m → n → o → p → q → r → s → t → u → v → w → x → y → z → a → b → c → d → e. This takes 5 steps, so it takes 5 seconds.
Move the pointer counterclockwise from 'l' to 'e', which is just going backward: l → k → j → i → h → g → f → e. This would take 7 steps, so it takes 7 seconds.

Moving clockwise again is the better choice because it takes fewer steps. So, the pointer moves to 'e', and typing 'e' takes 1 second.

Now, let’s move to 'a'. From 'e', we have:

Move the pointer clockwise from 'e' to 'a', which would take 5 steps: e → f → g → h → i → j → k → l → m → n → o → p → q → r → s → t → u → v → w → x → y → z. This would take 5 seconds.
Move the pointer counterclockwise from 'e' to 'a', which would take 4 steps: e → d → c → b → a. This would take 4 seconds.

In this case, moving counterclockwise is faster, so you choose that. The pointer moves to 'a', and typing 'a' takes 1 second.

Next, let’s move to 'r'. From 'a', we have:

Move the pointer clockwise from 'a' to 'r', which would take 17 steps: a → b → c → d → e → f → g → h → i → j → k → l → m → n → o → p → q → r. This would take 17 seconds.
Move the pointer counterclockwise from 'a' to 'r', which would take 9 steps: a → z → y → x → w → v → u → t → s → r. This would take 9 seconds.

Moving counterclockwise is faster, so the pointer moves to 'r', and typing 'r' takes 1 second.

Finally, let’s move to the last character, 'n'. From 'r', we have:

Move the pointer clockwise from 'r' to 'n', which would take 13 steps: r → s → t → u → v → w → x → y → z → a → b → c → d → e → f → g → h → i → j → k → l → m → n. This would take 13 seconds.
Move the pointer counterclockwise from 'r' to 'n', which would take 12 steps: r → q → p → o → n. This would take 12 seconds.

Again, moving counterclockwise is faster, so the pointer moves to 'n', and typing 'n' takes 1 second.

To summarize, here’s the breakdown of the time for each move:

From 'a' to 'l': 11 seconds
From 'l' to 'e': 5 seconds
From 'e' to 'a': 4 seconds
From 'a' to 'r': 9 seconds
From 'r' to 'n': 12 seconds

Total time = 11 + 5 + 4 + 9 + 12 = 41 seconds.

Now that we understand the greedy approach, the next question is that how do we calculate the time required in each direction (clockwise and counterclockwise). This is crucial because only by determining the time for both directions can we pick the minimum of the two and ensure we're making the optimal choice at every step.

How to calculate the Time required to move the pointer in each Direction?

If you move clockwise, you start at your current letter and go forward through the circle until you reach your target letter. For example, moving from ‘a’ to ‘d’ clockwise means you pass through ‘b’, 'c' and reach ‘d’. The number of steps you take in this direction is simply the difference in their positions.

When we subtract two characters (e.g., 'd' - 'a'), we get the distance between them in terms of how many steps forward they are in the alphabet. In programming, this works naturally because characters can be treated as values that have a fixed order and their relative positions in the alphabet are inherently numeric. This eliminates the need to manually map them to positions or think in terms of ASCII. It’s a direct and intuitive way to measure distances.

Example: To move from 'a' to 'd':
Subtract 'a' from 'd': d - a = 3.
This tells us that moving clockwise takes 3 steps.
Example: To move from 'b' to 'g':
Subtract 'b' from 'g': g - b = 5.
So, moving clockwise takes 5 steps.

Now, what about counterclockwise? This direction moves backward through the circle. If you’re at ‘a’ and want to go to ‘c’, counterclockwise means you go backward from ‘a’ all the way through ‘z’, and then forward until you reach ‘c’. While it sounds more complex, the distance can also be calculated easily. The counterclockwise distance is the total number of letters in the alphabet (26) minus the clockwise distance.

Example: To move from 'a' to 'd' counterclockwise:
Clockwise steps: 3.
Counterclockwise steps: 26 - 3 = 23.
So, moving counterclockwise takes 23 steps.
Example: To move from 'g' to 'b':
First, calculate the clockwise steps from 'g' to 'b':
Clockwise steps = b - g = -5 (negative because 'b' is before 'g').
In circular terms, this means: 26 + (-5) = 21.
Counterclockwise steps: 26 - 21 = 5.

Now that we’ve gone through the intuition, let’s summarize the process into a formula:

Compute the clockwise distance: abs(targetChar - currentChar).
Compute the counterclockwise distance: 26 - clockwiseDistance.
Choose the smaller value: min(clockwiseDistance,
counterclockwiseDistance).

Approach

Step 1: Initialize Variables
We need a variable to keep track of the total time taken to type the word. Let’s call it totalTime. Initially, it should be set to 0 because no time has been spent yet.
Since the pointer starts at 'a', we also need a variable to track the current position of the pointer. We’ll name it currentChar, and initialize it to 'a'. This will help us calculate the movement required to reach the next character in the word.

Step 2: Iterate Through Each Character of the Word
To type the word, we need to process each character one by one. We’ll use a loop that goes through all the characters in the string. In each iteration, we will:

Calculate the time it takes to move from the current character to the target character both clockwise and counterclockwise.
Clockwise Time: For two characters, currentChar and targetChar, the clockwise distance is calculated by finding the absolute difference between their positions in the alphabet. The formula is abs(targetChar - currentChar).
Counterclockwise Time: Find the clockwise distance using the above formula and then subtract this distance from the total number of characters in the alphabet, 26. This gives us the counterclockwise distance, which is calculated as 26 - clockwiseTime.
We’ll take the minimum of these two times: min(clockwiseTime, counterclockwiseTime).
Once we have the minimum distance, we add it to totalTime. This accounts for the time spent moving the pointer.
After that, we add 1 to totalTime for typing the target character.
The pointer needs to move to the target character after each operation. So, we set currentChar to targetChar at the end of each loop iteration.

Step 3: Return the Total Time
After the loop finishes, we will have processed all the characters in the word. At this point, the totalTime variable will contain the minimum time required to type the entire word. We simply return this value.

Dry Run

We begin with totalTime = 0, which means no time has been spent yet. The currentChar is 'a', as the pointer starts at 'a'.

The targetChar is 'a'.

The clockwise distance is calculated as the absolute difference between the ASCII values of 'a' and 'a', which is 0 (since the pointer is already on 'a').
The counterclockwise distance would be 26, as it’s the full circle of the alphabet.
The minimum of the clockwise and counterclockwise distances is 0, so no time is spent moving.
We add 1 second for typing 'a'. Thus, the totalTime becomes 1.
The pointer is now on 'a', so currentChar = 'a'.

Now, the targetChar is 'b'.

The clockwise distance is the absolute difference between the ASCII values of 'b' and 'a', which is 1.
The counterclockwise distance is calculated as 26 - 1 = 25, since we're going around the circle backward.
The minimum of the clockwise and counterclockwise distances is 1, so 1 second is added for moving the pointer.
We then add 1 second for typing 'b'. The totalTime becomes 3.
The pointer is now on 'b', so currentChar = 'b'.

Next, the targetChar is 'c'.

The clockwise distance between 'c' and 'b' is 1.
The counterclockwise distance is 26 - 1 = 25.
The minimum of the clockwise and counterclockwise distances is 1, so 1 second is added for moving the pointer.
We add 1 second for typing 'c'. The totalTime becomes 5.
The pointer is now on 'c', so currentChar = 'c'.

Final Result : After processing all characters in the word "abc", the totalTime is 5. This is the minimum time required to type the word using the circular typewriter.

Code for All Languages

C++

class Solution {
public:
    int minTimeToType(string word) {
    
        // Initialize total time required
        int totalTime = 0;

        // Pointer starts at 'a'
        char currentChar = 'a';

        // Iterate through each character in the word
        for (char targetChar : word) {
        
            // Calculate the clockwise distance
            int clockwiseTime = abs(targetChar - currentChar);

            // Calculate the counterclockwise distance
            int counterClockwiseTime = 26 - clockwiseTime;

            // Add the minimum of the two distances to the total time
            totalTime += min(clockwiseTime, counterClockwiseTime);

            // Add 1 second for typing the current character
            totalTime += 1;

            // Update the pointer to the current character
            currentChar = targetChar;
        }

        // Return the total time required
        return totalTime;
    }
};

Java

class Solution {
    public int minTimeToType(String word) {
        // Initialize total time required
        int totalTime = 0;

        // Pointer starts at 'a'
        char currentChar = 'a';

        // Iterate through each character in the word
        for (char targetChar : word.toCharArray()) {
            // Calculate the clockwise distance
            int clockwiseTime = Math.abs(targetChar - currentChar);

            // Calculate the counterclockwise distance
            int counterClockwiseTime = 26 - clockwiseTime;

            // Add the minimum of the two distances to the total time
            totalTime += Math.min(clockwiseTime, counterClockwiseTime);

            // Add 1 second for typing the current character
            totalTime += 1;

            // Update the pointer to the current character
            currentChar = targetChar;
        }

        // Return the total time required
        return totalTime;
    }
}

Python

class Solution:
    def minTimeToType(self, word: str) -> int:
        # Initialize total time required
        total_time = 0

        # Pointer starts at 'a'
        current_char = 'a'

        # Iterate through each character in the word
        for target_char in word:
            # Calculate the clockwise distance
            clockwise_time = abs(ord(target_char) - ord(current_char))

            # Calculate the counterclockwise distance
            counter_clockwise_time = 26 - clockwise_time

            # Add the minimum of the two distances to the total time
            total_time += min(clockwise_time, counter_clockwise_time)

            # Add 1 second for typing the current character
            total_time += 1

            # Update the pointer to the current character
            current_char = target_char

        # Return the total time required
        return total_time

Javascript

var minTimeToType = function(word) {
    // Initialize total time required
    let totalTime = 0;

    // Pointer starts at 'a'
    let currentChar = 'a';

    // Iterate through each character in the word
    for (let targetChar of word) {
        // Calculate the clockwise distance
        let clockwiseTime = Math.abs(targetChar.charCodeAt(0) - currentChar.charCodeAt(0));

        // Calculate the counterclockwise distance
        let counterClockwiseTime = 26 - clockwiseTime;

        // Add the minimum of the two distances to the total time
        totalTime += Math.min(clockwiseTime, counterClockwiseTime);

        // Add 1 second for typing the current character
        totalTime += 1;

        // Update the pointer to the current character
        currentChar = targetChar;
    }

    // Return the total time required
    return totalTime;
};

Time Complexity : O(n)

Loop: O(n)
The loop runs for each character in the word. If the word has n characters, the loop will execute n times.

Operations inside the Loop: O(1)
For each character in the word, we calculate the clockwise and counterclockwise distances. These are simple arithmetic operations involving subtraction and taking the absolute value, which all take constant time, O(1).

Final Time Complexity: O(n)
The total time complexity is O(n), where n is the number of characters in the word. This is because we perform a constant amount of work for each character in the word. Thus, the overall complexity is linear in relation to the length of the input word.

Space Complexity : O(1)

Auxiliary Space Complexity: O(1)
The auxiliary space refers to the extra space used by the algorithm apart from the input. In this case, we are using only a few variables:

totalTime (to keep track of the total time taken).
currentChar (to store the current character the pointer is on).

These variables require constant space, O(1).

Total Space Complexity: O(n)
The total space includes both the input and the auxiliary space.
The input string word takes O(n) space, where n is the number of characters in the word.
The algorithm does not use any additional space proportional to the size of the input, except for the constant variables.

Learning Tip

Now we have successfully tackled this problem, let's try these similar problems.

Minimum Operations to Make the Array Increasing

Given an integer array nums, determine the minimum number of increments needed to make the array strictly increasing, where nums[i] < nums[i+1] for all valid indices.

Maximum Sum With Exactly K Elements

You are given a 0-indexed integer array nums and an integer k. Your task is to perform the following operation exactly k times in order to maximize your score
1. Select an element m from nums.
2. Remove the selected element m from the array.
3. Add a new element with a value of m + 1 to the array.
4. Increase your score by m.

Preface

Online Judges

Time & Space Complexity

Control Flow Practice

Arrays Basics

String Basics

Matrix Basics

Math Basics

Recursion Basics

Sorting

Two Pointer

Prefix Sum

Matrix

Hashing

Sliding Window

Linked List

Stack

Queue

Binary Search

Bit Manipulation

Recursion and Backtracking

Trees

Heaps

Tries

Greedy

Dynamic Programming

Graphs

String Matching Algorithms

Combinatorics

Geometry

Game Theory

Advanced Algorithm