Single-Row Keyboard solution and explanation
Google
9 more videos on this problem
LeetCode 1165: Single-Row Keyboard - Interview Prep Ep 4Fisher Coder · 8:28 · 1K views
1165 Single Row KeyboardKelvin Chandra · 3:00 · 694 views
1165. Single-Row Keyboard - Week 1/5 Leetcode December ChallengeProgramming Live with Larry · 2:24 · 483 views
Live Coding: Leetcode 1165. Single-Row Keyboard (Leetcode easy)CS Live Coding · 8:04 · 239 views
LeetCode 1165. Single-Row Keyboard, mockingeazyleet · 11:42 · 158 views
Leetcode: Single-Row Keyboard (Easy)Lester Minnick · 5:54 · 152 views
1165. Single-Row Keyboard - Week 3/5 Leetcode January ChallengeProgramming Live with Larry · 2:53 · 145 views
LeetCode 1165: Single Row KeyboardEdgar Jr. San Martin · 14:27 · 62 views
LeetCode 1165 | Single-Row Keyboard | Counting Array | JavaSleepy Cracker · 4:28 · 58 views
Day 323 - Teaching Kids Programming - Single-Row Keyboard via Hash TableDoctor Lai · 12:00 · 31 views
The problem
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 == 26keyboardcontains each English lowercase letter exactly once in some order.1 <= word.length <= 104word[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.
class Solution:
def calculateTime(self, keyboard: str, word: str) -> int:
pos = {c: i for i, c in enumerate(keyboard)}
ans = i = 0
for c in word:
ans += abs(pos[c] - i)
i = pos[c]
return ansclass Solution {
public int calculateTime(String keyboard, String word) {
int[] pos = new int[26];
for (int i = 0; i < 26; ++i) {
pos[keyboard.charAt(i) - 'a'] = i;
}
int ans = 0, i = 0;
for (int k = 0; k < word.length(); ++k) {
int j = pos[word.charAt(k) - 'a'];
ans += Math.abs(i - j);
i = j;
}
return ans;
}
}class Solution {
public:
int calculateTime(string keyboard, string word) {
int pos[26];
for (int i = 0; i < 26; ++i) {
pos[keyboard[i] - 'a'] = i;
}
int ans = 0, i = 0;
for (char& c : word) {
int j = pos[c - 'a'];
ans += abs(i - j);
i = j;
}
return ans;
}
};function calculateTime(keyboard: string, word: string): number {
const pos: number[] = Array(26).fill(0);
for (let i = 0; i < 26; ++i) {
pos[keyboard.charCodeAt(i) - 97] = i;
}
let ans = 0;
let i = 0;
for (const c of word) {
const j = pos[c.charCodeAt(0) - 97];
ans += Math.abs(i - j);
i = j;
}
return ans;
}func calculateTime(keyboard string, word string) (ans int) {
pos := [26]int{}
for i, c := range keyboard {
pos[c-'a'] = i
}
i := 0
for _, c := range word {
j := pos[c-'a']
ans += abs(i - j)
i = j
}
return
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Linear scan of keyboard for every character | O(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 |
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.