LeetCode 1974 - Minimum Time to Type Word Using Special Typewriter

LeetCode Problem 1974

Difficulty: 🟢 Easy
Topics: String, Greedy

Solution

Problem Understanding

The problem describes a circular typewriter containing all lowercase English letters from 'a' to 'z'. A pointer moves around this circular arrangement, and initially the pointer starts at 'a'.

To type a character, the pointer must currently point at that character. Every action costs exactly one second. There are only two possible actions:

Move the pointer one step clockwise or counterclockwise.
Type the current character.

The goal is to determine the minimum number of seconds required to type the entire string word.

The important detail is that the letters are arranged in a circle. This means moving from 'a' to 'z' costs only one step counterclockwise, not twenty five steps clockwise. For every pair of consecutive characters, we must choose the shorter rotational direction.

The input is a single string word, and the output is the minimum total number of seconds needed to type all characters.

The constraints are very small:

1 <= word.length <= 100
Only lowercase English letters appear

Since there are only 26 letters and the word length is at most 100, performance is not a concern. Even inefficient solutions would likely pass. However, the problem is primarily about recognizing the circular distance optimization.

Several edge cases are important:

Typing the same character repeatedly, such as "aaa", where no movement is needed after the first character.
Moving across the circular boundary, such as from 'a' to 'z' or from 'z' to 'a'.
Words containing only one character.
Cases where counterclockwise movement is shorter than clockwise movement.

Approaches

Brute Force Approach

A brute force style solution would explicitly simulate both clockwise and counterclockwise movement for every character transition. For each target character, we could repeatedly move step by step in both directions until reaching the target, count the steps for each path, and choose the smaller value.

This works because the typewriter contains only 26 letters, so every possible movement path is finite and easy to simulate.

However, this approach performs unnecessary work because the circular distance can be computed directly using arithmetic. Instead of simulating movement one step at a time, we can calculate the clockwise distance and counterclockwise distance mathematically.

Optimal Greedy Approach

The key observation is that for any two letters, the minimum movement cost is simply:

The direct distance between their alphabet indices.
Or the wraparound distance through the circular boundary.

If the current pointer is at character current and we want to move to target, then:

direct_distance = abs(target - current)
wrap_distance = 26 - direct_distance

The minimum movement cost is:

min(direct_distance, wrap_distance)

After paying the movement cost, we always spend one additional second typing the character.

This greedy decision is optimal because each character transition is completely independent. There is never a reason to take a longer route since movement cost is additive and there are no future penalties or rewards.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * 26)	O(1)	Simulates clockwise and counterclockwise movement step by step
Optimal	O(n)	O(1)	Computes circular distance directly using arithmetic

Algorithm Walkthrough

Initialize the pointer position to 'a'.

The typewriter always starts at 'a', so this is our initial current character. 2. Initialize a variable to store the total time.

This variable accumulates both movement time and typing time. 3. Iterate through each character in word.

For every target character, determine how far the pointer must move. 4. Convert characters into numeric positions.

We can map letters to integers using ASCII values:

'a' -> 0
'b' -> 1
...
'z' -> 25

This allows easy arithmetic distance calculations. 5. Compute the direct alphabetical distance.

direct_distance = abs(target_position - current_position)

Compute the wraparound distance.

Since the letters form a circle of size 26:

wrap_distance = 26 - direct_distance

Add the smaller movement cost.

The pointer can move either clockwise or counterclockwise, so we choose the minimum. 8. Add one second for typing the character.

Every character requires exactly one typing operation. 9. Update the current pointer position.

After typing the character, the pointer now rests on that character. 10. Continue until all characters are processed. 11. Return the accumulated total time.

Why it works

For every transition between characters, the shortest possible movement is either the direct path or the wraparound path around the circle. Since movement costs are independent between transitions, choosing the locally minimal movement for each step also minimizes the total time globally. Adding one second per character accounts for the required typing operation.

Python Solution

class Solution:
    def minTimeToType(self, word: str) -> int:
        current_position = 0  # 'a'
        total_time = 0

        for char in word:
            target_position = ord(char) - ord('a')

            direct_distance = abs(target_position - current_position)
            wrap_distance = 26 - direct_distance

            total_time += min(direct_distance, wrap_distance)

            # One second to type the character
            total_time += 1

            current_position = target_position

        return total_time

The implementation follows the algorithm directly.

The variable current_position tracks where the pointer currently is on the circular keyboard. Since the pointer starts at 'a', the initial value is 0.

For every character in the input word, the code converts the character into its alphabetical index using:

ord(char) - ord('a')

The code then computes two possible movement distances:

The direct alphabetical distance.
The wraparound distance through the circular boundary.

The smaller of the two values is added to the total time. After movement, one additional second is added for typing the character itself.

Finally, the current pointer position is updated so the next iteration starts from the correct location.

Go Solution

func minTimeToType(word string) int {
	currentPosition := 0
	totalTime := 0

	for _, char := range word {
		targetPosition := int(char - 'a')

		directDistance := targetPosition - currentPosition
		if directDistance < 0 {
			directDistance = -directDistance
		}

		wrapDistance := 26 - directDistance

		if directDistance < wrapDistance {
			totalTime += directDistance
		} else {
			totalTime += wrapDistance
		}

		// One second to type the character
		totalTime++

		currentPosition = targetPosition
	}

	return totalTime
}

The Go implementation mirrors the Python logic closely.

One notable difference is that Go does not provide a built in abs() function for integers, so the absolute value must be computed manually.

The loop iterates over the string using Go runes, though this problem only contains lowercase ASCII letters. Integer overflow is not a concern because the maximum possible answer is very small.

Worked Examples

Example 1: `word = "abc"`

Initial state:

Pointer at 'a'
Total time = 0

Step	Current	Target	Direct Distance	Wrap Distance	Movement Cost	Typing Cost	Total Time
1	a	a	0	26	0	1	1
2	a	b	1	25	1	1	3
3	b	c	1	25	1	1	5

Final answer: 5

Example 2: `word = "bza"`

Initial state:

Pointer at 'a'
Total time = 0

Step	Current	Target	Direct Distance	Wrap Distance	Movement Cost	Typing Cost	Total Time
1	a	b	1	25	1	1	2
2	b	z	24	2	2	1	5
3	z	a	25	1	1	1	7

Final answer: 7

Example 3: `word = "zjpc"`

Initial state:

Pointer at 'a'
Total time = 0

Step	Current	Target	Direct Distance	Wrap Distance	Movement Cost	Typing Cost	Total Time
1	a	z	25	1	1	1	2
2	z	j	16	10	10	1	13
3	j	p	6	20	6	1	20
4	p	c	13	13	13	1	34

Final answer: 34

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is processed exactly once
Space	O(1)	Only a few integer variables are used

The algorithm scans through the input word one time. Every iteration performs only constant time arithmetic operations, so the total running time grows linearly with the length of the string.

The space usage remains constant because no additional data structures proportional to the input size are allocated.

Test Cases

solution = Solution()

assert solution.minTimeToType("abc") == 5        # Basic forward movement
assert solution.minTimeToType("bza") == 7        # Uses wraparound movement
assert solution.minTimeToType("zjpc") == 34      # Mixed clockwise/counterclockwise

assert solution.minTimeToType("a") == 1          # Already at starting position
assert solution.minTimeToType("z") == 2          # Single wraparound move
assert solution.minTimeToType("aa") == 2         # No movement needed after first char
assert solution.minTimeToType("aaa") == 3        # Repeated same character

assert solution.minTimeToType("az") == 3         # Wraparound from a to z
assert solution.minTimeToType("za") == 4         # Wraparound in opposite direction

assert solution.minTimeToType("abcdefghijklmnopqrstuvwxyz") > 0
# Full alphabet traversal

assert solution.minTimeToType("leetcode") > 0
# General mixed case

assert solution.minTimeToType("mmmm") == 14
# First move to m, then repeated typing

Test	Why
`"abc"`	Simple sequential movement
`"bza"`	Validates circular wraparound optimization
`"zjpc"`	Tests mixed movement directions
`"a"`	Smallest possible input
`"z"`	Single counterclockwise wraparound
`"aa"`	Repeated character without movement
`"aaa"`	Multiple repeated characters
`"az"`	Boundary transition from beginning to end
`"za"`	Boundary transition from end to beginning
`"abcdefghijklmnopqrstuvwxyz"`	Full traversal across all letters
`"leetcode"`	General realistic example
`"mmmm"`	Large initial movement followed by repeated typing

Edge Cases

Repeated Characters

An input like "aaa" can expose bugs where implementations incorrectly add movement cost even when the pointer is already on the correct character.

In this case, the direct distance is zero, so the algorithm adds only the typing cost for each character. The implementation handles this naturally because:

abs(target_position - current_position)

evaluates to zero when both positions are identical.

Circular Boundary Movement

The most important edge case is movement between 'a' and 'z'. A naive implementation might move twenty five steps clockwise instead of one step counterclockwise.

The algorithm explicitly handles this by computing:

wrap_distance = 26 - direct_distance

This ensures the shorter circular path is always chosen.

Single Character Input

A one character input such as "a" or "z" is the minimum possible input size.

The algorithm still works correctly because the loop processes exactly one character. For "a", movement cost is zero and typing cost is one. For "z", the algorithm correctly identifies that moving one step counterclockwise is cheaper than moving twenty five steps clockwise.

LeetCode 1974 - Minimum Time to Type Word Using Special Typewriter

Solution

Problem Understanding

Approaches

Brute Force Approach

Optimal Greedy Approach

Algorithm Walkthrough

Why it works

Python Solution

Go Solution

Worked Examples

Example 1: word = "abc"

Example 2: word = "bza"

Example 3: word = "zjpc"

Complexity Analysis

Test Cases

Edge Cases

Repeated Characters

Circular Boundary Movement

Single Character Input

Example 1: `word = "abc"`

Example 2: `word = "bza"`

Example 3: `word = "zjpc"`