# 1165. Single-Row Keyboard

## Description

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.

## Solutions

Solution 1: Hash Table or Array

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 {
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;
}
};

• 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 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
}

• 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;
}