Minimum Time to Type Word Using Special Typewriter

Easy
1190.

Minimum Time to Type Word Using Special Typewriter

Minimum Time to Type Word Using Special Typewriter is an easy coding problem on strings and greedy, asked in Amazon and Google interviews.

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 <= 100
  • word consists of lowercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} word
 * @return {number}
 */
var minTimeToType = function(word) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 100
  • word consists of lowercase English letters

Hints for Minimum Time to Type Word Using Special Typewriter

  1. Hint 1

    Each letter is reached from the previous one independently, so add the costs letter by letter.

  2. Hint 2

    Between two letters d apart in the alphabet, one direction costs d moves and the other 26 - d.

  3. 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

  1. Start with the pointer at 'a' and total = 0.
  2. For each letter c: let d = |c - prev|; add min(d, 26 - d) moves plus 1 second to type.
  3. Set prev = c and continue.
  4. 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 a to z is 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 total

Java

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