💬 Discord
Sign In
NeetCode #14LC-1165EasyArrays & HashingNC Algo100
← Back to All Problems

#14 · #1165 · Single-Row Keyboard(单行键盘)

📌 Problem Statement & Constraints

A robot has one finger and types on a single-row keyboard. It starts with the finger on the key at index 0. Given keyboard (a permutation of 26 lowercase letters) and word, return the total time to type word, where moving from index i to index j takes |i - j| time. Constraints: keyboard.length == 26, 1 <= word.length <= 10^4.

💡 Core Algorithmic Approaches

  1. Build a position map from letter to its index on the keyboard -- this is the whole trick, turning each lookup into O(1).
  2. Track the finger's current index, initialised to 0.
  3. For each character of word, add abs(target - current) to the total and move the finger.
  4. Without the position map, each character would require a linear scan of the keyboard.

💻 Benchmark Python3 Implementation

class Solution:
    def calculateTime(self, keyboard: str, word: str) -> int:
        pos = {ch: i for i, ch in enumerate(keyboard)}
        cur = 0                            # finger starts at index 0
        total = 0
        for ch in word:
            total += abs(pos[ch] - cur)
            cur = pos[ch]
        return total

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(26 + |word|) = O(|word|): building the map is constant work, then one step per character.
💾 Space Complexity
O(1): the position map has exactly 26 entries.

⚠️ Interview Pitfalls & Follow-ups

  • Initialising the finger at the position of the first character: it starts at index 0, so the first move counts.
  • Using keyboard.index(ch) inside the loop: O(26) per character, giving O(26 * |word|). Correct but wasteful; precompute the map.
  • Forgetting abs: the finger can move in either direction.