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.

#1974

Easy

auto_awesome贪心·invariant

LeetCode 题解工作台

使用特殊打字机键入单词的最少时间

有一个特殊打字机，它由一个圆盘和一个指针组成，圆盘上标有小写英文字母 'a' 到 'z' 。只有当指针指向某个字母时，它才能被键入。指针初始时指向字符 'a' 。每一秒钟，你可以执行以下操作之一：将指针顺时针或者逆时针移动一个字符。键入指针当前指向的字符。给你一…

字符串贪心

题目描述

有一个特殊打字机，它由一个圆盘和一个指针组成，圆盘上标有小写英文字母 'a' 到 'z'。只有当指针指向某个字母时，它才能被键入。指针 初始时 指向字符 'a' 。

每一秒钟，你可以执行以下操作之一：

将指针 顺时针 或者 逆时针 移动一个字符。
键入指针当前指向的字符。

给你一个字符串 word ，请你返回键入 word 所表示单词的最少秒数。

示例 1：

输入：word = "abc"
输出：5
解释：
单词按如下操作键入：
- 花 1 秒键入字符 'a'，因为指针初始指向 'a' ，故不需移动指针。
- 花 1 秒将指针顺时针移到 'b' 。
- 花 1 秒键入字符 'b' 。
- 花 1 秒将指针顺时针移到 'c' 。
- 花 1 秒键入字符 'c' 。

示例 2：

输入：word = "bza"
输出：7
解释：
单词按如下操作键入：
- 花 1 秒将指针顺时针移到 'b' 。
- 花 1 秒键入字符 'b' 。
- 花 2 秒将指针逆时针移到 'z' 。
- 花 1 秒键入字符 'z' 。
- 花 1 秒将指针顺时针移到 'a' 。
- 花 1 秒键入字符 'a' 。

示例 3：

输入：word = "zjpc"
输出：34
解释：
单词按如下操作键入：
- 花 1 秒将指针逆时针移到 'z' 。
- 花 1 秒键入字符 'z' 。
- 花 10 秒将指针顺时针移到 'j' 。
- 花 1 秒键入字符 'j' 。
- 花 6 秒将指针顺时针移到 'p' 。
- 花 1 秒键入字符 'p' 。
- 花 13 秒将指针逆时针移到 'c' 。
- 花 1 秒键入字符 'c' 。

提示：

1 <= word.length <= 100
word 只包含小写英文字母。

lightbulb

解题思路

方法一：贪心

我们初始化答案变量 $\textit{ans}$ 为字符串的长度，表示我们至少需要 $\textit{ans}$ 秒来键入字符串。

接下来，我们遍历字符串，对于每个字符，我们计算当前字符和前一个字符之间的最小距离，将这个距离加到答案中。然后我们更新当前字符为前一个字符，继续遍历。

时间复杂度 $O(n)$ ，其中 $n$ 为字符串的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The interviewer emphasizes there are only two directions between letters, which points to taking min(clockwise, counterclockwise) on each transition.
question_mark
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.
question_mark
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.

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#1963 使字符串平衡的最小交换次数 #1946 子字符串突变后可能得到的最大整数 #2014 重复 K 次的最长子序列