Total Distance to Type a String Using One Finger - Solution & Explanation

Problem Overview: You get a keyboard layout string containing all 26 lowercase letters and a target word. Typing starts at the first character of the word. Every move between letters costs the absolute distance between their indices on the keyboard. The task is to compute the total distance your finger travels while typing the entire word.

Approach 1: Linear Search Simulation (O(26 * n) time, O(1) space)

Simulate typing directly. For each character in the word, scan the keyboard string to find its index. Compute the distance from the previous character’s position using abs(currIndex - prevIndex) and add it to the total. This works because the keyboard size is fixed at 26, but it still performs a full scan for each character. The logic is simple but inefficient compared to precomputing positions.

Approach 2: Hash Table Index Mapping (O(n) time, O(26) space)

Precompute the index of every character in the keyboard using a hash table. Iterate through the keyboard once and store char → index. Then iterate through the word and calculate the distance between consecutive characters using the stored indices. Each lookup is O(1), so the total runtime becomes linear in the word length. This is the most common implementation in interviews because it clearly shows preprocessing plus constant‑time lookup.

Approach 3: Array Mapping Optimization (O(n) time, O(1) space)

Instead of a hash map, use a fixed array of size 26 where index = char - 'a'. Populate the array with keyboard positions during a single pass. When processing the word, retrieve each character’s keyboard index directly from the array and accumulate the distance. This avoids hash overhead and keeps memory constant. The technique is a lightweight simulation pattern often used in string and keyboard‑layout problems.

Recommended for interviews: Use the index mapping approach with a hash map or array. It runs in O(n) time and demonstrates good preprocessing habits. The brute simulation shows you understand the problem mechanics, but interviewers expect you to remove the repeated keyboard scans and achieve constant‑time lookups using hashing or indexing.