Minimum Time to Type Word Using Special Typewriter Solution
Minimum Time to Type Word Using Special Typewriter solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Minimum Time to Type Word Using Special Typewriter is an easy coding problem on strings and greedy, asked in Amazon and Google interviews.
- Difficulty: Easy
- Topics: Strings, Greedy
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A special typewriter has the letters 'a' to 'z' arranged on a circle, with a pointer that starts at 'a'. Each second you may do exactly one of:
- move the pointer one letter clockwise or one letter counterclockwise (the circle wraps, so
'z'and'a'are neighbours); - type the letter the pointer is on.
Return the minimum number of seconds needed to type the string word.
Example 1
Input: word = "kai"
Output: 31
Explanation: a→k takes 10 moves, k→a takes 10, a→i takes 8, plus 3 seconds of typing.
Example 2
Input: word = "zz"
Output: 3
Explanation: One counterclockwise move to `z`, then type it twice.
Example 3
Input: word = "a"
Output: 1
Constraints
1 <= word.length <= 100word consists of lowercase English letters
Hints for Minimum Time to Type Word Using Special Typewriter
Hint 1
Each letter is reached from the previous one independently, so add the costs letter by letter.
Hint 2
Between two letters
dapart in the alphabet, one direction costsdmoves and the other26 - d.Hint 3
Total = sum over letters of
min(d, 26 - d) + 1, starting from'a'.
How to solve Minimum Time to Type Word Using Special Typewriter
Typing a letter only depends on where the pointer was, so the optimal plan moves the shorter way round the circle to each letter in turn and types it.
Approach
- Start with the pointer at
'a'andtotal = 0. - For each letter
c: letd = |c - prev|; addmin(d, 26 - d)moves plus 1 second to type. - Set
prev = cand continue. - Return
total.
Why it works
The pointer must visit the letters of word in order, and the only cost between consecutive letters is the movement. On a circle of 26 positions the two ways round cost d and 26 - d, so the shorter one is optimal for that leg, and the legs do not interact because each starts exactly where the previous one ended.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- The pointer starts at
'a', so the first letter also costs movement. - Count one second per typed letter, including repeats with zero movement.
- Remember the wrap-around: from
atozis one move, not 25.
Reference solution
Python
def minTimeToType(word: str) -> int:
total = 0
prev = 'a'
for c in word:
d = abs(ord(c) - ord(prev))
total += min(d, 26 - d) + 1
prev = c
return totalJava
public static int minTimeToType(String word) {
int total = 0;
char prev = 'a';
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
int d = Math.abs(c - prev);
total += Math.min(d, 26 - d) + 1;
prev = c;
}
return total;
}C++
int minTimeToType(string word) {
int total = 0;
char prev = 'a';
for (char c : word) {
int d = abs(c - prev);
total += min(d, 26 - d) + 1;
prev = c;
}
return total;
}JavaScript
var minTimeToType = function(word) {
var total = 0, prev = 97;
for (var i = 0; i < word.length; i++) {
var c = word.charCodeAt(i);
var d = Math.abs(c - prev);
total += Math.min(d, 26 - d) + 1;
prev = c;
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Greedy Algorithms