We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Single-Row Keyboard

Number: 1123

Difficulty: Easy

Paid? Yes

Companies: Google

Problem Description

A special keyboard has all keys arranged in a single row. Given a string called keyboard of length 26 representing the keyboard layout (each letter appears exactly once) and a word to type, calculate the total time needed to type that word. The time to move from one key to another is defined as the absolute difference between their indices. Initially, your finger is at index 0.

Key Insights

  • Create a mapping (hash table/dictionary) from each character to its index on the keyboard for O(1) lookups.
  • The cost to type each character is the absolute difference between the current position and the target character's position on the keyboard.
  • Start from index 0 and sum up the distances moved for each successive character in the word.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the word. Space Complexity: O(1) (constant space for a mapping of 26 characters).

Solution

We solve the problem by first building a dictionary that maps each character in the keyboard layout to its corresponding index. We then initialize a variable to track the current finger position (starting at 0). For each character in the word, we look up its index, calculate the absolute difference from the current position, add that distance to the total time, and update the current position. This approach uses a single pass over the word with constant time lookups, ensuring an efficient solution.

Code Solutions

# Build a dictionary to map each character to its index in the keyboard string.
def calculateTime(keyboard: str, word: str) -> int:
    # Create a mapping for character to index
    char_index = {char: idx for idx, char in enumerate(keyboard)}
    
    # Initialize the total time and starting position
    total_time = 0
    current_position = 0
    
    # Iterate over each character in the word
    for char in word:
        # Find the target index for the character
        target_position = char_index[char]
        # Calculate the time to move to the target position
        total_time += abs(target_position - current_position)
        # Update current position to the target position
        current_position = target_position
        
    return total_time

# Example usage:
# print(calculateTime("abcdefghijklmnopqrstuvwxyz", "cba"))
← Back to All Questions