Minimum Time to Type Word Using Special Typewriter
EasyEditorial · 5 minGenerated by the editor · Aug 25
Open — the attempt gate is not wired up yet
This editorial is meant to unlock after you have run the problem at least once, with the worked solution behind one further deliberate click. That needs per-learner unlock state nothing stores today, so for now the whole article is open.
Intuitionwhy each character can be solved independently
Typing a character always costs exactly one second, so the only choice is how to move the pointer from its current letter to the next required letter. On a circle, two routes connect those letters: clockwise and counterclockwise. You should take the shorter route, because movement for one target does not change the required order or the cost of any later target once you arrive.
After reaching and typing one character, that character becomes the starting point for the next move. Therefore, process the word from left to right, keep the current pointer letter, and add the shorter circular distance plus one typing second for every character. Choosing a longer route can never help: both routes finish on the same letter, and all future decisions start from that same position.
The circle gives two possible movement distances, and the smaller one is always sufficient.
Approach
1Set the answer to zero and place the current pointer at a, because the typewriter starts there and every distance must be measured from the pointer's actual position.
2For each character c in word, compute the ordinary alphabet distance between c and the current letter, because that distance is the number of steps along one direction before wrapping is considered.
3Compare that distance with 26 minus the distance, because the two values represent the clockwise and counterclockwise routes around all 26 letters.
4Add the smaller route length to the answer, because taking the longer route reaches the same target while spending extra seconds.
5Add one more second for typing c, because arriving at a letter and pressing the typewriter are separate actions.
6Set the current letter to c after accounting for it, because the next character's movement begins where this character was typed.
7Return the accumulated answer after the scan, because every character has been typed exactly once and no later rearrangement can reduce any chosen movement.
Complexityone pass and constant working memory
MEASURE
BOUND
WHY
Time
O(n)
The loop processes each character once and performs a constant number of arithmetic operations for it. The pointer moves conceptually, but the solution counts the distance directly instead of simulating each step, so no movement step is processed repeatedly.
Space
O(1)
Only the current letter and the answer are stored. The returned integer is required output and is excluded from extra space; the bound remains O(1) for every word, including the longest allowed input.
Here n is the length of word.
Annotated solutionC++ · one-pass greedy scan
CPPCompute the shorter circular route and add one typing second for each character.
#include <algorithm>
#include <cstdlib>
#include <string>
using namespace std;
class Solution {
public:
int minTimeToType(string word) {
int ans = 0;
char cur = 'a';
for (char c : word) {
int diff = abs(c - cur);
ans += min(diff, 26 - diff) + 1;
cur = c;
}
return ans;
}
};
The expression min(diff, 26 - diff) is the heart of the solution. The direct alphabet gap gives one route, while the remaining letters on the circle give the route in the opposite direction. Updating cur only after adding the cost makes each iteration measure exactly the move from the previously typed character to the new one.