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.

Description Hints 4 Solution Video 8:28

1165. Single-Row Keyboard

Easy87.6% acceptance1 companyPremium elsewhere, free here

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 <= 10⁴
word[i] is an English lowercase letter.

Asked at 1 company

Google

Topics

Hash Table String

Hints open one at a time

Hint 1

Can be the problem divided in parts, so solving each part and sum their solutions it should return the answer? Yes, you only need to divide the problem in finger jumps.

Hint 2

In each finger jump you need to move your finger from one character to another, you need to know its index.

Hint 3

Map each character to it's index.

Hint 4

Use a hash table to do that.

8:28

Still stuck?Read the written solution, or watch a walkthrough.

Open solution