Problem Description

The Single-Row Keyboard problem asks you to determine the total typing time for a string, given a custom keyboard layout. The keyboard consists of a single row of 26 lowercase English letters arranged in a custom order, provided as a string keyboard. You are also given a word word that you want to type using this keyboard.

The typing time for each character is defined as the absolute difference between the indices of the current and previous characters on the keyboard. Typing the first character starts at index 0. The goal is to compute the total time required to type the entire word.

• Each character in keyboard is unique and appears exactly once.
• All characters in word are lowercase English letters.
• There is only one valid solution for each input.
• Do not reuse or skip characters; type them in order as they appear in word.

Thought Process

The problem can be approached by simulating the process of typing each character in the word on the custom keyboard. For each character, we need to know its position on the keyboard and calculate how far we need to move from the previous character.

A brute-force approach would be to search for the position of each character in keyboard every time we need it. However, this would be inefficient as it would require scanning the keyboard string repeatedly.

To optimize, we can first create a mapping from each character to its index in the keyboard (using a hash map or array). This allows us to retrieve any character's position in constant time. Then, as we iterate through word, we can quickly compute the movement cost for each character and sum these to get the total time.

Solution Approach

• Step 1: Build the Keyboard Mapping
  • Create a mapping (e.g., a hash map or array) that associates each character in keyboard with its index.
  • This allows for O(1) lookup of any character's position.
• Step 2: Initialize Typing Position
  • Start with the typing position at index 0 (the beginning of the keyboard).
  • Initialize a variable to keep track of the total time.
• Step 3: Iterate Through the Word
  • For each character in word:
  • Look up its position in the keyboard mapping.
  • Calculate the absolute difference between the current and previous positions.
  • Add this difference to the total time.
  • Update the previous position to the current character's position.
• Step 4: Return the Result
  • After processing all characters, return the total time as the answer.

This approach is efficient because the mapping is built once and reused, making each character lookup and movement calculation very fast.

Example Walkthrough

Example:
keyboard = "abcdefghijklmnopqrstuvwxyz"
word = "cba"

1. Build the keyboard mapping:
   • 'a' → 0, 'b' → 1, 'c' → 2, ..., 'z' → 25
2. Type 'c':
   • Start at position 0 (before typing).
   • 'c' is at index 2.
   • Movement: |2 - 0| = 2
   • Total time so far: 2
3. Type 'b':
   • Previous position: 2
   • 'b' is at index 1.
   • Movement: |1 - 2| = 1
   • Total time so far: 3
4. Type 'a':
   • Previous position: 1
   • 'a' is at index 0.
   • Movement: |0 - 1| = 1
   • Total time so far: 4

Final Answer: 4

Time and Space Complexity

• Brute-force approach:
  • For each character in word, scan keyboard to find its index.
  • If n is the length of word, and m is the length of keyboard (26), time complexity is O(n * m).
• Optimized approach (with mapping):
  • Building the mapping: O(26) = O(1) (since the keyboard always has 26 letters).
  • Processing the word: O(n), where n is the length of word.
  • Total time complexity: O(n)
  • Space complexity: O(1), since the mapping size is fixed (26 letters).

Summary

The Single-Row Keyboard problem is efficiently solved by first building a mapping from each letter to its index in the custom keyboard. This allows constant-time lookups for each character in the word, making the total time proportional to the word's length. The key insight is to avoid repeated searches by using a hash map or array for the keyboard layout, which leads to a clean and optimal O(n) solution. This approach demonstrates the power of preprocessing and direct indexing in algorithmic problem solving.

Code Implementation

class Solution:
    def calculateTime(self, keyboard: str, word: str) -> int:
        # Build mapping from character to index
        pos = {ch: i for i, ch in enumerate(keyboard)}
        time = 0
        prev = 0
        for ch in word:
            time += abs(pos[ch] - prev)
            prev = pos[ch]
        return time
      

class Solution {
public:
    int calculateTime(string keyboard, string word) {
        vector<int> pos(26);
        for (int i = 0; i < 26; ++i) {
            pos[keyboard[i] - 'a'] = i;
        }
        int time = 0, prev = 0;
        for (char ch : word) {
            time += abs(pos[ch - 'a'] - prev);
            prev = pos[ch - 'a'];
        }
        return time;
    }
};
      

class Solution {
    public int calculateTime(String keyboard, String word) {
        int[] pos = new int[26];
        for (int i = 0; i < 26; ++i) {
            pos[keyboard.charAt(i) - 'a'] = i;
        }
        int time = 0, prev = 0;
        for (char ch : word.toCharArray()) {
            time += Math.abs(pos[ch - 'a'] - prev);
            prev = pos[ch - 'a'];
        }
        return time;
    }
}
      

var calculateTime = function(keyboard, word) {
    const pos = {};
    for (let i = 0; i < keyboard.length; ++i) {
        pos[keyboard[i]] = i;
    }
    let time = 0, prev = 0;
    for (let ch of word) {
        time += Math.abs(pos[ch] - prev);
        prev = pos[ch];
    }
    return time;
};