easy Minimum Time to Type Word Using Special Typewriter

Problem Statement

You are given a circular keyboard that has all the lowercase English letters ('a' to 'z') laid out in a circle. You can type a particular character if the point is pointed to that character. Initially, a cursor points at the letter 'a'.

At each second, you can perform the following operation:

• Move the cursor either one step to the left or right.
• Type the letter where the pointer points currently.

Given a string word, return the minimum number of seconds to type out the characters in a word.

Examples

• Example 1:

  • Input: "bad"
  • Expected Output: 8
  • Justification: Start at 'a'. Move to 'b' (1 second), type 'b' (1 second), move to 'a' (1 seconds), type 'a' (1 second), move to 'd' from 'a' (3 second), and type 'd' (1 second). Total = 8 seconds.

• Example 2:

  • Input: "zigzag"
  • Expected Output: 32
  • Justification: Start at 'a'. Move to 'z' (1 second), type 'z' (1 second), move to 'i' (9 seconds, choosing the shorter path), type 'i' (1 second), move to 'g' (2 seconds), type 'g' (1 second), move to 'z' (7 seconds), type 'z' (1 second), move to 'a' (1 second), and type 'a' (1 second), move to 'g' (6 seconds), type 'g' (1 second). Total = 32 seconds.

• Example 3:

  • Input: "ace"
  • Expected Output: 7
  • Justification: Start at 'a', type 'a' (1 second), move to 'c' (2 seconds), type 'c' (1 second), move to 'e' (2 seconds), and type 'e' (1 second). Total = 7 seconds.

Solution

To solve this problem, we adopt a strategy that minimizes the movement around the circular keyboard. For each letter in the target word, we calculate the minimum distance from the current letter to the target letter, considering both clockwise and counterclockwise movements.

This approach ensures that we always take the shortest path to the next letter, significantly reducing the total time taken to type the word. The time taken to type each letter is constant, so our primary focus is on minimizing cursor movement. This method is effective because it leverages the circular nature of the keyboard layout, ensuring that we exploit the shortest possible route to each letter, which is inherently the most efficient approach for this particular problem.

Step-by-Step Algorithm

1. Initialize Variables:

   • totalTime to 0, which will hold the total time taken to type the word.
   • previousChar to 'a', representing the starting point of the typewriter cursor.

2. Iterate Through Each Character of the Word:

   • For each character currentChar in the input word, perform the following steps:

3. Calculate Distance:

   • Determine the ASCII value difference between currentChar and previousChar to find the direct distance distance between them.

4. Calculate Steps:

   • Compute the clockwise and counterclockwise steps required to move from previousChar to currentChar. This is done by taking the minimum of distance and 26 - distance (total letters in the alphabet minus the direct distance), ensuring the shortest path is chosen.

5. Update Total Time:

   • Add the calculated steps plus one (for typing the character) to totalTime. The "+1" accounts for the action of typing the current character.

6. Update Previous Character:

   • Set previousChar to the current character currentChar to prepare for the next iteration.

7. Return Total Time:

   • After iterating through all characters in the word, return totalTime as the total time taken to type the word.

Algorithm Walkthrough

Consider the input word "zigzag" for the algorithm walkthrough:

• Initialize:

  • totalTime = 0
  • previousChar = 'a'

• For 'z':

  • currentChar = 'z'
  • distance = abs('z' - 'a') = 25
  • steps = min(25, 26 - 25) = 1 (shortest path is 1 step)
  • totalTime += 1 (move) + 1 (type) = 2
  • previousChar = 'z'

• For 'i':

  • currentChar = 'i'
  • distance = abs('i' - 'z') = 9
  • steps = min(9, 26 - 9) = 9
  • totalTime += 9 (move) + 1 (type) = 12
  • previousChar = 'i'

• For 'g':

  • currentChar = 'g'
  • distance = abs('g' - 'i') = 2
  • steps = min(2, 26 - 2) = 2
  • totalTime += 2 (move) + 1 (type) = 15
  • previousChar = 'g'

• For 'z' (again):

  • currentChar = 'z'
  • distance = abs('z' - 'g') = 7
  • steps = min(7, 26 - 7) = 7
  • totalTime += 7 (move) + 1 (type) = 23
  • previousChar = 'z'

• For 'a':

  • currentChar = 'a'
  • distance = abs('a' - 'z') = 1 (since 'z' to 'a' is a direct step)
  • steps = min(1, 26 - 1) = 1
  • totalTime += 1 (move) + 1 (type) = 25
  • previousChar = 'a'

• For 'g' (again):

  • currentChar = 'g'
  • distance = abs('g' - 'a') = 6
  • steps = min(6, 26 - 6) = 6
  • totalTime += 6 (move) + 1 (type) = 32
  • previousChar = 'g'

• Final Total Time: 32 seconds

Code

public class Solution {

  public int minTimeToType(String word) {
    int totalTime = 0; // Initialize total time
    char previousChar = 'a'; // Start from 'a'

    for (char currentChar : word.toCharArray()) {
      // Calculate the minimum steps needed to reach currentChar from previousChar
      int distance = Math.abs(currentChar - previousChar);
      int steps = Math.min(distance, 26 - distance) + 1; // +1 for typing the character
      totalTime += steps; // Update total time
      previousChar = currentChar; // Update previousChar for the next iteration
    }

    return totalTime;
  }

  public static void main(String[] args) {
    Solution solution = new Solution();
    // Test the method with example inputs
    System.out.println(solution.minTimeToType("bad")); // 8
    System.out.println(solution.minTimeToType("zigzag")); // 32
    System.out.println(solution.minTimeToType("ace")); // 7
  }
}

Complexity Analysis

Time Complexity

• : The primary operation in the algorithm is iterating through each character of the input string, where (n) is the length of the string. For each character, we perform constant time operations, which do not depend on the size of the string. Thus, the overall time complexity is linear relative to the length of the input string.

Space Complexity

• : The space complexity is constant because the amount of memory used does not scale with the size of the input.