1165. Single-Row Keyboard - Explanation

Problem Link

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 = "neetcode"

Output: 77

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.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Storing indexes for all letters

class Solution:
    def calculateTime(self, keyboard: str, word: str) -> int:
        key_indices = {}
        # Get the index for each key.
        for i in range(len(keyboard)):
            key_indices[keyboard[i]] = i
            
        # Initialize previous index as starting index = 0.
        prev = 0
        result = 0
        
        # Calculate the total time.
        for c in word:
            # Add the distance from previous index
            # to current letter's index to the result.
            result += abs(prev - key_indices[c])
            
            # Update the previous index to current index for next iteration.
            prev = key_indices[c]
            
        return result

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(1)$ constant space

Where $n$ is the length of word.