#1974

Easy

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Minimum Time to Type Word Using Special Typewriter

Compute the minimum typing time by greedily taking the shorter circular move between consecutive letters, then adding one second per character.

string greedy

Problem Statement

You start with a circular typewriter whose pointer begins at letter a. To type a target word, each character must be reached by rotating the pointer around the 26-letter ring, and each move by one adjacent position costs one second. Typing the current letter also costs one second, so every character contributes a press plus whatever travel is needed from the previous pointer position.

The key detail in this problem is that every transition between two letters has exactly two candidate paths: clockwise and counterclockwise. The task is to total the minimum travel cost across all adjacent letter transitions in the word, beginning from a, while making sure each chosen move is the shorter circular route before counting the typing action.

Examples

Example 1

Input: word = "abc"

Output: 5

The characters are printed as follows:

Type the character 'a' in 1 second since the pointer is initially on 'a'.
Move the pointer clockwise to 'b' in 1 second.
Type the character 'b' in 1 second.
Move the pointer clockwise to 'c' in 1 second.
Type the character 'c' in 1 second.

Example 2

Input: word = "bza"

Output: 7

The characters are printed as follows:

Move the pointer clockwise to 'b' in 1 second.
Type the character 'b' in 1 second.
Move the pointer counterclockwise to 'z' in 2 seconds.
Type the character 'z' in 1 second.
Move the pointer clockwise to 'a' in 1 second.
Type the character 'a' in 1 second.

Example 3

Input: word = "zjpc"

Output: 34

The characters are printed as follows:

Move the pointer counterclockwise to 'z' in 1 second.
Type the character 'z' in 1 second.
Move the pointer clockwise to 'j' in 10 seconds.
Type the character 'j' in 1 second.
Move the pointer clockwise to 'p' in 6 seconds.
Type the character 'p' in 1 second.
Move the pointer counterclockwise to 'c' in 13 seconds.
Type the character 'c' in 1 second.

Constraints

1 <= word.length <= 100
word consists of lowercase English letters.

Solution Approach

Model each step as a circular distance decision

Track the pointer as the previous character, starting from a. For each next character in the word, convert both letters to positions 0 through 25 and compute the absolute gap. Because the keyboard is circular, the real movement cost is the smaller of gap and 26 minus gap. This is the entire greedy choice for LeetCode 1974.

Add movement and typing in one pass

Scan the word once. For every character, add the minimum circular move from the current pointer to that character, then add 1 for typing. After that, update the pointer to the typed character. This works because the problem never rewards taking a longer route now to save time later; the next state depends only on the current letter you end on.

Validate the invariant with examples

After processing index i, the pointer must be on word[i], and the accumulated total must be the minimum possible time to get there and type everything through that position. For word = abc, the moves are 0, 1, and 1, plus 3 presses, giving 5. For word = bza, the best transitions are a to b with cost 1, b to z with cost 2, and z to a with cost 1, then add 3 presses for 7 total.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The best approach runs in O(n) time because it examines each character once and does O(1) work per transition. It uses O(1) space because it stores only the running total, the current pointer position, and a few temporary distance values.

What Interviewers Usually Probe

The interviewer emphasizes there are only two directions between letters, which points to taking min(clockwise, counterclockwise) on each transition.
If they ask why greedy is safe, they want you to state that each step has no future trade-off because the only carried state is the current letter.
If they ask for an invariant, explain that after each processed character, your total is already minimal for typing the prefix and ending at that exact pointer position.

Common Pitfalls or Variants

Common pitfalls

Forgetting the initial pointer starts at a, which makes the first transition different from later ones.
Using only absolute difference and missing the wraparound path such as a to z costing 1 instead of 25.
Counting movement correctly but forgetting that every typed character adds an extra 1 second.

Follow-up variants

Return the actual sequence of clockwise or counterclockwise moves, not just the minimum time.
Change the alphabet size or layout so the circular distance formula must use k instead of 26.
Assign different costs to rotation and typing, which keeps the same transition idea but changes the total formula.

FAQ

What is the main pattern in Minimum Time to Type Word Using Special Typewriter?

The pattern is greedy choice plus invariant validation. For each next letter, choose the shorter of the two circular directions, then maintain the invariant that the prefix has been typed in minimum time and the pointer ends on the current character.

Why is a greedy step enough for LeetCode 1974?

A longer move to the current letter never creates a better future state, because after typing that letter the only state that matters is the letter itself. Since both short and long routes end at the same position, taking the smaller movement cost is always optimal.

How do you compute the movement between two letters?

Map each letter to 0 through 25. Let gap be the absolute difference between the two positions. The minimum rotation cost is min(gap, 26 - gap).

Why does word = abc return 5?

You start on a, so typing a costs 1 with no movement. Then move to b in 1 and type in 1, then move to c in 1 and type in 1. The total is 1 + 1 + 1 + 1 + 1 = 5.

What are the time and space costs of the best solution?

The optimal implementation is O(n) time and O(1) space. You only scan the word once and keep a running total plus the current pointer position.

terminal

Solution

Solution 1: Greedy

We initialize the answer variable $\textit{ans}$ to the length of the string, indicating that we need at least $\textit{ans}$ seconds to type the string.

class Solution:
    def minTimeToType(self, word: str) -> int:
        ans, a = len(word), ord("a")
        for c in map(ord, word):
            d = abs(c - a)
            ans += min(d, 26 - d)
            a = c
        return ans

Continue Practicing

#1963 minimum number of swaps to make the string balanced #1946 largest number after mutating substring #2014 longest subsequence repeated k times