Using greedy without proof
Wrong move: Locally optimal choices may fail globally.
Usually fails on: Counterexamples appear on crafted input orderings.
Fix: Verify with exchange argument or monotonic objective before committing.
Build confidence with an intuition-first walkthrough focused on greedy fundamentals.
There is a special typewriter with lowercase English letters 'a' to 'z' arranged in a circle with a pointer. A character can only be typed if the pointer is pointing to that character. The pointer is initially pointing to the character 'a'.
Each second, you may perform one of the following operations:
Given a string word, return the minimum number of seconds to type out the characters in word.
Example 1:
Input: word = "abc" Output: 5 Explanation: 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 Explanation: 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 Explanation: 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 <= 100word consists of lowercase English letters.Problem summary: There is a special typewriter with lowercase English letters 'a' to 'z' arranged in a circle with a pointer. A character can only be typed if the pointer is pointing to that character. The pointer is initially pointing to the character 'a'. Each second, you may perform one of the following operations: Move the pointer one character counterclockwise or clockwise. Type the character the pointer is currently on. Given a string word, return the minimum number of seconds to type out the characters in word.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Greedy
"abc"
"bza"
"zjpc"
minimum-distance-to-type-a-word-using-two-fingers)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1974: Minimum Time to Type Word Using Special Typewriter
class Solution {
public int minTimeToType(String word) {
int ans = word.length();
char a = 'a';
for (char c : word.toCharArray()) {
int d = Math.abs(a - c);
ans += Math.min(d, 26 - d);
a = c;
}
return ans;
}
}
// Accepted solution for LeetCode #1974: Minimum Time to Type Word Using Special Typewriter
func minTimeToType(word string) int {
ans := len(word)
a := rune('a')
for _, c := range word {
d := int(max(a-c, c-a))
ans += min(d, 26-d)
a = c
}
return ans
}
# Accepted solution for LeetCode #1974: Minimum Time to Type Word Using Special Typewriter
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
// Accepted solution for LeetCode #1974: Minimum Time to Type Word Using Special Typewriter
struct Solution;
impl Solution {
fn min_time_to_type(word: String) -> i32 {
let mut current = b'a';
let mut res = 0;
for b in word.bytes() {
if b == current {
res += 1;
} else {
let d = if b > current {
b - current
} else {
current - b
};
let d = d.min(26 - d);
current = b;
res += d as i32 + 1;
}
}
res
}
}
#[test]
fn test() {
let word = "abc".to_string();
let res = 5;
assert_eq!(Solution::min_time_to_type(word), res);
let word = "bza".to_string();
let res = 7;
assert_eq!(Solution::min_time_to_type(word), res);
let word = "zjpc".to_string();
let res = 34;
assert_eq!(Solution::min_time_to_type(word), res);
}
// Accepted solution for LeetCode #1974: Minimum Time to Type Word Using Special Typewriter
function minTimeToType(word: string): number {
let a = 'a'.charCodeAt(0);
let ans = word.length;
for (const c of word) {
const d = Math.abs(c.charCodeAt(0) - a);
ans += Math.min(d, 26 - d);
a = c.charCodeAt(0);
}
return ans;
}
Use this to step through a reusable interview workflow for this problem.
Try every possible combination of choices. With n items each having two states (include/exclude), the search space is 2ⁿ. Evaluating each combination takes O(n), giving O(n × 2ⁿ). The recursion stack or subset storage uses O(n) space.
Greedy algorithms typically sort the input (O(n log n)) then make a single pass (O(n)). The sort dominates. If the input is already sorted or the greedy choice can be computed without sorting, time drops to O(n). Proving greedy correctness (exchange argument) is harder than the implementation.
Review these before coding to avoid predictable interview regressions.
Wrong move: Locally optimal choices may fail globally.
Usually fails on: Counterexamples appear on crafted input orderings.
Fix: Verify with exchange argument or monotonic objective before committing.