Watch 10 video solutions for Single-Row Keyboard, a easy level problem involving Hash Table, String. This walkthrough by Fisher Coder has 1,513 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
There is a special keyboard with all keys in a single row.
Given a string keyboard of length 26 indicating the layout of the keyboard (indexed from 0 to 25). Initially, your finger is at index 0. To type a character, you have to move your finger to the index of the desired character. The time taken to move your finger from index i to index j is |i - j|.
You want to type a string word. Write a function to calculate how much time it takes to type it with one finger.
Example 1:
Input: keyboard = "abcdefghijklmnopqrstuvwxyz", word = "cba" Output: 4 Explanation: The index moves from 0 to 2 to write 'c' then to 1 to write 'b' then to 0 again to write 'a'. Total time = 2 + 1 + 1 = 4.
Example 2:
Input: keyboard = "pqrstuvwxyzabcdefghijklmno", word = "leetcode" Output: 73
Constraints:
keyboard.length == 26keyboard contains each English lowercase letter exactly once in some order.1 <= word.length <= 104word[i] is an English lowercase letter.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.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Linear scan of keyboard for every character | O(26 * n) | O(1) | Simple baseline solution when you do not precompute character positions |
| Precomputed index map (Array or Hash Table) | O(n) | O(1) | Best approach for interviews and production due to constant-time lookups |