algoadvance

Leetcode 1974. Minimum Time to Type Word Using Special Typewriter

Problem Statement

You are given a string word consisting of lowercase English letters. In one second, you can perform one of the following operations:

The pointer initially points to the character ‘a’. Each time a character needs to be typed from word, you need to move the pointer based on the shortest path (clockwise or counterclockwise) to that character.

Return the minimum number of seconds to type out the entire word.

Clarifying Questions

  1. Is the typewriter circular? Yes, the typewriter is circular, meaning after ‘z’ it wraps around back to ‘a’ and vice versa.

  2. Can the same key be typed more than once? Yes, each character in the word needs to be typed in order, regardless of repetitions.

  3. What is the length of the string word? The string word can be up to 100 characters long.

Strategy

  1. Initialize the pointer at ‘a’.
  2. Iterate over each character of the word.
  3. Calculate the clockwise and counterclockwise distances from the current position to the target character.
  4. Choose the minimum distance to type the character.
  5. Add this minimum distance and 1 (for typing the character) to the total time.
  6. Update the current position to the new character after typing.

Code

public class MinimumTimeToTypeWord {
    public int minTimeToType(String word) {
        int totalTime = 0;
        char current = 'a';
        
        for (char c : word.toCharArray()) {
            int clockwiseDist = Math.abs(c - current);
            int counterClockwiseDist = 26 - clockwiseDist;
            totalTime += Math.min(clockwiseDist, counterClockwiseDist) + 1;
            current = c;
        }
        
        return totalTime;
    }

    public static void main(String[] args) {
        MinimumTimeToTypeWord obj = new MinimumTimeToTypeWord();
        String word = "cba";
        System.out.println("Minimum time to type \"" + word + "\": " + obj.minTimeToType(word));
    }
}

Time Complexity

The time complexity of this solution is O(n), where n is the length of the string word. This is because we are iterating through each character of the string exactly once.

Explanation

  1. We initialize totalTime to 0 and start at the character ‘a’.
  2. For each character in the word, we calculate two distances:
    • Clockwise distance: Math.abs(c - current)
    • Counter-clockwise distance: 26 - clockwiseDistance
  3. We add the minimum of the two distances plus 1 (for typing the character) to the totalTime.
  4. We update the current position to the new character after typing it.

This approach ensures that we use the minimum time to move between characters and include the time to type each character.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI