Single-Row Keyboard

Easy · Arrays & Hashing · Explanation and code example

Storing indexes for all letters

How it works

To type a word efficiently, we need to know where each key is located on the keyboard. By precomputing the position of every letter, we can quickly look up the distance between consecutive characters. The total time is the sum of all these distances as we move from one key to the next.

Steps

  1. Create a mapping from each character in the keyboard to its index position.
  2. Initialize prev to 0 (starting position) and result to 0.
  3. For each character in the word:
    • Look up its position and add the absolute distance from prev to result.
    • Update prev to the current character's position.
  4. Return result as the total typing time.

Complexity

  • Time complexity: O(n)
  • Space complexity: O(1) constant space

Where n is the length of word.

Things to watch for

Forgetting to Track the Previous Position

A common mistake is calculating the distance from a fixed starting point (like index 0) for each character instead of from the previous character's position. The finger moves sequentially through the word, so each distance calculation must be relative to where the finger currently is.

Not Using Absolute Value for Distance

When calculating the distance between two positions, forgetting to take the absolute value leads to negative distances when moving left on the keyboard. The time to move is always the magnitude of the difference, regardless of direction.

Python code example

class Solution:
    def calculateTime(self, keyboard: str, word: str) -> int:
        key_indices = {}
        # Get the index for each key.
        for i in range(len(keyboard)):
            key_indices[keyboard[i]] = i
            
        # Initialize previous index as starting index = 0.
        prev = 0
        result = 0
        
        # Calculate the total time.
        for c in word:
            # Add the distance from previous index
            # to current letter's index to the result.
            result += abs(prev - key_indices[c])
            
            # Update the previous index to current index for next iteration.
            prev = key_indices[c]
            
        return result

C++ code example

class Solution {
public:
    int calculateTime(string keyboard, string word) {
        vector<int> keyIndices(26, -1);

        // Get the index for each key.
        for (int i = 0; i < keyboard.length(); i++)
            keyIndices[keyboard[i] - 'a'] = i;

        // Initialize previous index as starting index = 0.
        int prev = 0;
        int result = 0;

        // Calculate the total time.
        for (char &c : word) {
            // Add the distance from previous index
            // to current letter's index to the result.
            result += abs(prev - keyIndices[c - 'a']);

            // Update the previous index to current index for next iteration.
            prev = keyIndices[c - 'a'];
        }
        return result;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations