Domain 1EasyCORE

Single-Row Keyboard

The problem involves calculating the time taken to type a given word on a single-row keyboard. The keyboard layout is provided as a string of length 26, where each character represents a key in some order. Initially, the finger starts at index 0. To type a character, the finger must move from its current position to the position of the desired character on the keyboard. The time taken for this movement is the absolute difference between the indices.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#String

1165. Single-Row Keyboard

Model: qwen2.5-coder:14b
Topics: String
FAANG asked: 1
Acceptance rate: 85.4%


Problem Breakdown

The problem involves calculating the time taken to type a given word on a single-row keyboard. The keyboard layout is provided as a string of length 26, where each character represents a key in some order. Initially, the finger starts at index 0. To type a character, the finger must move from its current position to the position of the desired character on the keyboard. The time taken for this movement is the absolute difference between the indices.

Inputs:

  • keyboard: A string of length 26 representing the layout of the keyboard.
  • word: A string representing the word to be typed.

Outputs:

  • An integer representing the total time taken to type the word.

Implicit Constraints/Edge Cases:

  • The keyboard contains each English lowercase letter exactly once.
  • The word can be empty, in which case the time should be 0.
  • The word length is between 1 and 10^4 characters.

Intuition

The brute-force approach would involve iterating through the word and for each character, finding its position on the keyboard, then calculating the distance from the previous character’s position. This approach has a time complexity of O(n * m), where n is the length of the word and m is the length of the keyboard (which is constant 26).

A better approach is to preprocess the keyboard to create a mapping from each character to its index. This allows us to look up the index in constant time, reducing the overall complexity to O(n). The key insight is that by storing the positions of all characters, we can quickly compute the distance between consecutive characters in the word.

Approach

  1. Preprocessing: Create a dictionary char_to_index where each character in the keyboard maps to its index.
  2. Initialization: Start with the initial finger position at index 0 and initialize a variable total_time to 0.
  3. Iteration: For each character in the word:
    • Find its index using the char_to_index dictionary.
    • Calculate the time taken to move from the current position to this character’s index.
    • Update the total time by adding the calculated distance.
    • Move the finger to the new position.
  4. Return: The total time accumulated.

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the word. This is because we iterate through the word once and perform constant-time operations for each character.
  • Space Complexity: O(1) for storing the char_to_index dictionary, as its size is fixed at 26.

Solution

def calculate_typing_time(keyboard: str, word: str) -> int:
    # Preprocess the keyboard to create a mapping from character to index
    char_to_index = {char: idx for idx, char in enumerate(keyboard)}
    
    # Initialize total time and starting position
    total_time = 0
    current_position = 0
    
    # Iterate through each character in the word
    for char in word:
        # Find the target index of the character
        target_index = char_to_index[char]
        
        # Calculate the time taken to move from current position to target index
        total_time += abs(target_index - current_position)
        
        # Update the current position to the target index
        current_position = target_index
    
    return total_time

Edge Cases Handled

  • Empty Word: If the word is empty, the function returns 0 immediately since no typing is required.
  • Single Character Word: The function correctly calculates the time for a single character by moving from the initial position (0) to the character’s position.
  • All Characters in Order: If the word consists of characters that appear consecutively on the keyboard, the total time is simply the sum of their indices.
  • All Characters in Reverse Order: Similarly, if the word consists of characters in reverse order, the function calculates the correct time by considering the distances between consecutive characters.