Skip to main content
Talentd

Single-Row Keyboard - Solution & Explanation

EasyPremiumFree on FleetCodeHash TableString8 min readAsked at: Google
Practice this problem

Problem Statement

There is a special keyboard with all keys in a single row.

Given a string keyboard of length 26 indicating the layout of the keyboard (indexed from 0 to 25). Initially, your finger is at index 0. To type a character, you have to move your finger to the index of the desired character. The time taken to move your finger from index i to index j is |i - j|.

You want to type a string word. Write a function to calculate how much time it takes to type it with one finger.

 

Example 1:

Input: keyboard = "abcdefghijklmnopqrstuvwxyz", word = "cba"
Output: 4
Explanation: The index moves from 0 to 2 to write 'c' then to 1 to write 'b' then to 0 again to write 'a'.
Total time = 2 + 1 + 1 = 4.

Example 2:

Input: keyboard = "pqrstuvwxyzabcdefghijklmno", word = "leetcode"
Output: 73

 

Constraints:

  • keyboard.length == 26
  • keyboard contains each English lowercase letter exactly once in some order.
  • 1 <= word.length <= 104
  • word[i] is an English lowercase letter.

Approach Overview

Problem Overview: You get a keyboard layout represented by a string of 26 lowercase letters arranged in a single row. Typing a word requires moving your finger along this row. The cost of typing each character equals the absolute distance between the previous character’s index and the current one. Compute the total typing time for the given word.

Approach 1: Linear Search for Each Character (O(26 * n) time, O(1) space)

The direct method scans the keyboard string every time you need the index of a character. Start with the finger at position 0. For each character in the word, iterate through the keyboard to find its index, then add abs(currentIndex - previousIndex) to the total time. This works because the keyboard length is fixed (26), so each lookup is small but still repeated for every character. The downside is unnecessary repeated scans, which makes the approach slower for long words.

Approach 2: Precomputed Position Map using Array or Hash Table (O(n) time, O(1) space)

A faster solution builds a direct mapping from character to index before processing the word. Iterate through the keyboard once and store each character’s position in an array (size 26) or a hash table. Now each character lookup becomes O(1). Traverse the word, fetch the index of each character from the map, compute the distance from the previous index, and accumulate the result. This avoids repeated scans and processes the word in a single pass.

This approach relies on constant-time lookups and simple arithmetic operations. The algorithm mainly uses sequential traversal of the string and direct index access, making it both simple and efficient. Since the keyboard size is fixed, the auxiliary storage is constant.

Recommended for interviews: The array or hash table mapping approach is the expected solution. Mentioning the naive scan shows you understand the baseline, but building a position map demonstrates awareness of lookup optimization and reduces the complexity to linear time.

Solution

We can use a hash table or an array pos of length 26 to store the position of each character on the keyboard, where pos[c] represents the position of character c on the keyboard.

Then we traverse the string word, using a variable i to record the current position of the finger, initially i = 0. Each time, we calculate the position j of the current character c on the keyboard, and increase the answer by |i - j|, then update i to j. Continue to traverse the next character until the entire string word is traversed.

After traversing the string word, we can get the answer.

The time complexity is O(n), and the space complexity is O(C). Here, n is the length of the string word, and C is the size of the character set. In this problem, C = 26.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Linear scan of keyboard for every characterO(26 * n)O(1)Simple baseline solution when you do not precompute character positions
Precomputed index map (Array or Hash Table)O(n)O(1)Best approach for interviews and production due to constant-time lookups

Video Solution

LeetCode 1165: Single-Row Keyboard - Interview Prep Ep 4 • Fisher Coder • 1,519 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Single-Row Keyboard easy or hard?
Single-Row Keyboard is rated Easy on LeetCode with a high acceptance rate. The main idea is recognizing that repeated character lookups should be optimized using a precomputed index map.
Single-Row Keyboard Python/Java solution
Most implementations build a dictionary or array mapping characters to indices, then iterate through the word calculating absolute index differences. The logic is identical across Python, Java, C++, Go, and TypeScript because it relies only on array indexing and simple arithmetic.
How to solve Single-Row Keyboard in O(n)?
First create a mapping from each character in the keyboard string to its index. Then iterate through the target word, retrieve the index for each character, and add the absolute difference from the previous index to the total typing time. Because each lookup is O(1), the entire traversal of the word runs in O(n).
What is the best approach for Single-Row Keyboard?
The optimal approach builds a direct mapping from each character to its index in the keyboard using an array or hash table. After preprocessing the keyboard in O(26) time, iterate through the word and compute the distance between consecutive character positions. This reduces the total complexity to O(n) time with O(1) extra space.
Is Single-Row Keyboard asked at Google/Amazon/Meta?
Single-Row Keyboard is categorized as an easy string and hash table problem and appears frequently in coding practice sets. Variations of character indexing and keyboard distance problems are common in screening rounds at companies like Amazon and Google.
What data structure is used in Single-Row Keyboard?
The typical solution uses an array of size 26 or a hash table to map characters to their positions in the keyboard string. This allows constant-time lookups while processing the word and avoids repeatedly scanning the keyboard layout.
What is the time complexity of Single-Row Keyboard?
The optimal solution runs in O(n) time where n is the length of the word. Each character position is retrieved in constant time from a precomputed array or hash map, and the algorithm performs a single pass through the word.

Ready to solve this problem?

Practice Single-Row Keyboard with our built-in code editor and test cases.

Practice on FleetCode
Previous

Total Distance to Type a String Using One Finger