Solution Explanation: Single-Row Keyboard

This problem involves calculating the total time taken to type a word on a keyboard with keys arranged in a single row. The time taken to move between keys is the absolute difference between their indices.

Approach

The solution uses a hash table (or array) to efficiently map each character to its index on the keyboard. This allows for quick lookups of character positions. The algorithm iterates through the input word:

1. Initialization: A hash table pos is created to store the index of each character in the keyboard string. The initial finger position i is set to 0. The total time ans is initialized to 0.

2. Iteration: The code iterates through each character c in the word string.

3. Position Lookup: For each character, its index j in the keyboard is retrieved from the pos hash table using pos[c].

4. Time Calculation: The time taken to move from the current position i to the new position j is calculated as abs(i - j) and added to the total time ans.

5. Position Update: The current finger position i is updated to the new position j.

6. Return Value: After processing all characters in the word, the total time ans is returned.

Time and Space Complexity

• Time Complexity: O(n), where n is the length of the word string. The algorithm iterates through the word once, performing constant-time operations for each character.

• Space Complexity: O(1). The hash table pos has a fixed size of 26 (number of characters in the alphabet), making its space usage constant. While technically dependent on the alphabet size, this is treated as constant in algorithmic analysis.

Code Implementation (Python)

class Solution:
    def calculateTime(self, keyboard: str, word: str) -> int:
        pos = {c: i for i, c in enumerate(keyboard)} #Hash table creation O(1) space
        ans = i = 0 #initializations O(1) time
        for c in word: #Iterating over word O(n) time
            ans += abs(pos[c] - i) #Calculating time difference O(1) time
            i = pos[c] #updating position O(1) time
        return ans #return O(1) time

The Python code directly implements the described algorithm. Other language implementations (Java, C++, Go, TypeScript) follow a similar structure, differing only in syntax and data structure specifics. All maintain the same time and space complexity characteristics.