Minimum Time to Type Word Using Special Typewriter - Solution & Explanation

Problem Overview: You start with a pointer on character 'a' of a circular typewriter containing the letters a to z. For each character in the target word, rotate the pointer either clockwise or counterclockwise to reach the letter, then press the key to type it. The goal is to compute the minimum total time required.

Approach 1: Simple Circular Distance Calculation (Greedy) (Time: O(n), Space: O(1))

The alphabet forms a circle of 26 characters. Moving from one letter to another has two possible paths: clockwise and counterclockwise. For each character in the word, compute the distance from the current pointer position using abs(curr - target). The opposite direction distance is 26 - diff. Choose the smaller value and add 1 second for pressing the key. Update the pointer to the typed character and continue scanning the string.

This works because each step is independent. The optimal move between two letters is always the shorter circular distance. No dynamic programming or backtracking is required. The algorithm simply iterates once through the word, making it linear time. This problem mainly tests understanding of circular distance calculations in string problems and applying a straightforward greedy decision at every step.

Approach 2: Prefix Sum Optimization (Time: O(n), Space: O(n))

If multiple distance queries were required, you could precompute cumulative rotation costs using a prefix structure. Convert each character into an index from 0–25 and precompute distances between adjacent characters in the word. A prefix sum array stores cumulative typing cost so that partial ranges can be evaluated quickly. Each transition still uses the same circular distance formula, but prefix sums make it easy to reuse computed movement costs.

For this specific problem the prefix sum approach does not improve asymptotic complexity. The word is processed once and each step is constant work, so the greedy scan is already optimal. Prefix sums mainly demonstrate how repeated movement computations could be aggregated when the problem expands to multiple queries or substring evaluations. It connects with common preprocessing patterns used in string traversal problems.

Recommended for interviews: The greedy circular distance solution is what interviewers expect. It shows you recognized the alphabet is a ring and minimized rotation using min(diff, 26 - diff). Mentioning the prefix-sum idea demonstrates awareness of preprocessing techniques, but the O(n) greedy scan is the clean and optimal implementation.