Single-Row Keyboard

We need to calculate the total time taken to type a given word, considering a specific layout of the keyboard. We will determine the time by calculating the absolute difference between the indices of consecutive characters in the word.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def calculateTime(self, keyboard: str, word: str) -> int:
        index_map = {char: idx for idx, char in enumerate(keyboard)}
        time_taken = 0
        current_index = 0

        for char in word:
            next_index = index_map[char]
            time_taken += abs(next_index - current_index)
            current_index = next_index

        return time_taken

Explanation

1. We first create a dictionary index_map that maps each character in the keyboard to its index. This helps us quickly find the index of a character in the word.
2. We initialize two variables: time_taken to keep track of the total time taken and current_index to keep track of the current position of the finger.
3. We loop through each character in the word and calculate the absolute difference between the current index and the next index of the character in the word. This difference represents the time taken to move the finger from one character to the next.
4. We update current_index to the next index for the following iteration.
5. Finally, we return the total time taken.

By using the dictionary to store the index of each character, we ensure that the lookup time is constant, leading to an efficient solution.

title: Single-Row Keyboard excerpt: Constant space solution for Single-Row Keyboard problem. tags: linear-scan relative-position-of-element

First Attempt

The first attempt only passes the first test case:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def calculate_time(keyboard, word)
  output = 0
  
  for i in (0..word.size-1)
    j = keyboard.index(word[i])

    output += (j - i).abs
  end
  
  output
end

The first index is 0, this must be changed in every iteration to the position of the character we just typed.

Working Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def calculate_time(keyboard, word)
  output = 0
  start = 0
  
  for i in (0..word.size-1)
    j = keyboard.index(word[i])
    
    output += (j - start).abs
    start = j
  end
  
  output
end

Time Complexity: O(N * K)

Where N is the word size and K is the keyboard size. Keyboard length is 26, so the runtime is linear.

Space Complexity: O(1).

If we cannot use the language specific method like index, we can use a hash table.

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

def calculate_time(keyboard, word)
  output = 0
  start = 0
  
  index = {}
  chars = keyboard.chars
  for i in (0..chars.size-1)
    index[chars[i]] = i
  end
  
  for i in (0..word.size-1)
    j = index[word[i]]
    
    output += (j - start).abs
    start = j
  end
  
  output
end

Time: O(N), where N is the size of the word. Space: O(1), because we only need to store 26 and this does not increase when the input size increases.