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
- Preprocessing: Create a dictionary
char_to_indexwhere each character in the keyboard maps to its index. - Initialization: Start with the initial finger position at index 0 and initialize a variable
total_timeto 0. - Iteration: For each character in the word:
- Find its index using the
char_to_indexdictionary. - 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.
- Find its index using the
- 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_indexdictionary, 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.