0% completed
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
eitherone step
to theleft
orright
.- 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.
- Input:
-
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.
- Input:
-
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.
- Input:
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
-
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.
-
Iterate Through Each Character of the Word:
- For each character
currentChar
in the input word, perform the following steps:
- For each character
-
Calculate Distance:
- Determine the ASCII value difference between
currentChar
andpreviousChar
to find the direct distancedistance
between them.
- Determine the ASCII value difference between
-
Calculate Steps:
- Compute the clockwise and counterclockwise steps required to move from
previousChar
tocurrentChar
. This is done by taking the minimum ofdistance
and26 - distance
(total letters in the alphabet minus the direct distance), ensuring the shortest path is chosen.
- Compute the clockwise and counterclockwise steps required to move from
-
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.
- Add the calculated steps plus one (for typing the character) to
-
Update Previous Character:
- Set
previousChar
to the current charactercurrentChar
to prepare for the next iteration.
- Set
-
Return Total Time:
- After iterating through all characters in the word, return
totalTime
as the total time taken to type the word.
- After iterating through all characters in the word, return
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
Complexity Analysis
Time Complexity
- O(n): 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
- O(1): The space complexity is constant because the amount of memory used does not scale with the size of the input.
.....
.....
.....
Table of Contents
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible