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.

Examples

Example 1:

1
2
3
4

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:

1
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^4
  • word[i] is an English lowercase letter.

Solution

Method 1 – Index Mapping and Linear Scan

Intuition

Map each character to its index in the keyboard. For each character in word, compute the distance from the previous character’s index.

Approach

  1. Build a map from character to index for the keyboard.
  2. Start at index 0. For each character in word, add the distance from the previous index to the answer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

#include <string>
#include <vector>
using namespace std;
class Solution {
public:
    int calculateTime(string keyboard, string word) {
        vector<int> pos(26);
        for (int i = 0; i < 26; ++i) pos[keyboard[i]-'a'] = i;
        int ans = 0, prev = 0;
        for (char c : word) {
            int idx = pos[c-'a'];
            ans += abs(idx - prev);
            prev = idx;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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, prev = 0;
        for (char c : word.toCharArray()) {
            int idx = pos[c-'a'];
            ans += Math.abs(idx - prev);
            prev = idx;
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9

class Solution:
    def calculateTime(self, keyboard: str, word: str) -> int:
        pos = {c: i for i, c in enumerate(keyboard)}
        ans = prev = 0
        for c in word:
            idx = pos[c]
            ans += abs(idx - prev)
            prev = idx
        return ans

Complexity

  • ⏰ Time complexity: O(n) — n = len(word), plus O(1) for keyboard mapping.
  • 🧺 Space complexity: O(1) — Only a fixed-size map/array is used.