Single-Row Keyboard - Solution & Explanation

Problem Overview: You get a keyboard layout represented by a string of 26 lowercase letters arranged in a single row. Typing a word requires moving your finger along this row. The cost of typing each character equals the absolute distance between the previous character’s index and the current one. Compute the total typing time for the given word.

Approach 1: Linear Search for Each Character (O(26 * n) time, O(1) space)

The direct method scans the keyboard string every time you need the index of a character. Start with the finger at position 0. For each character in the word, iterate through the keyboard to find its index, then add abs(currentIndex - previousIndex) to the total time. This works because the keyboard length is fixed (26), so each lookup is small but still repeated for every character. The downside is unnecessary repeated scans, which makes the approach slower for long words.

Approach 2: Precomputed Position Map using Array or Hash Table (O(n) time, O(1) space)

A faster solution builds a direct mapping from character to index before processing the word. Iterate through the keyboard once and store each character’s position in an array (size 26) or a hash table. Now each character lookup becomes O(1). Traverse the word, fetch the index of each character from the map, compute the distance from the previous index, and accumulate the result. This avoids repeated scans and processes the word in a single pass.

This approach relies on constant-time lookups and simple arithmetic operations. The algorithm mainly uses sequential traversal of the string and direct index access, making it both simple and efficient. Since the keyboard size is fixed, the auxiliary storage is constant.

Recommended for interviews: The array or hash table mapping approach is the expected solution. Mentioning the naive scan shows you understand the baseline, but building a position map demonstrates awareness of lookup optimization and reduces the complexity to linear time.