Skip to main content
Talentd

Total Distance to Type a String Using One Finger - Solution & Explanation

MediumPremiumFree on FleetCodeHash TableString8 min read
Practice this problem

Problem Statement

There is a special keyboard where keys are arranged in a rectangular grid as follows.
q w e r t y u i o p
a s d f g h j k l  
z x c v b n m      

You are given a string s that consists of lowercase English letters only. Return an integer denoting the total distance to type s using only one finger. Your finger starts on the key 'a'.

The distance between two keys at (r1, c1) and (r2, c2) is |r1 - r2| + |c1 - c2|.

 

Example 1:

Input: s = "hello"

Output: 17

Explanation:

  • Your finger starts at 'a', which is at (1, 0).
  • Move to 'h', which is at (1, 5). The distance is |1 - 1| + |0 - 5| = 5.
  • Move to 'e', which is at (0, 2). The distance is |1 - 0| + |5 - 2| = 4.
  • Move to 'l', which is at (1, 8). The distance is |0 - 1| + |2 - 8| = 7.
  • Move to 'l', which is at (1, 8). The distance is |1 - 1| + |8 - 8| = 0.
  • Move to 'o', which is at (0, 8). The distance is |1 - 0| + |8 - 8| = 1.
  • Total distance is 5 + 4 + 7 + 0 + 1 = 17.

Example 2:

Input: s = "a"

Output: 0

Explanation:

  • Your finger starts at 'a', which is at (1, 0).
  • Move to 'a', which is at (1, 0). The distance is |1 - 1| + |0 - 0| = 0.
  • Total distance is 0.

 

Constraints:

  • 1 <= s.length <= 104
  • s consists of lowercase English letters only.

Approach Overview

Problem Overview: You get a keyboard layout string containing all 26 lowercase letters and a target word. Typing starts at the first character of the word. Every move between letters costs the absolute distance between their indices on the keyboard. The task is to compute the total distance your finger travels while typing the entire word.

Approach 1: Linear Search Simulation (O(26 * n) time, O(1) space)

Simulate typing directly. For each character in the word, scan the keyboard string to find its index. Compute the distance from the previous character’s position using abs(currIndex - prevIndex) and add it to the total. This works because the keyboard size is fixed at 26, but it still performs a full scan for each character. The logic is simple but inefficient compared to precomputing positions.

Approach 2: Hash Table Index Mapping (O(n) time, O(26) space)

Precompute the index of every character in the keyboard using a hash table. Iterate through the keyboard once and store char → index. Then iterate through the word and calculate the distance between consecutive characters using the stored indices. Each lookup is O(1), so the total runtime becomes linear in the word length. This is the most common implementation in interviews because it clearly shows preprocessing plus constant‑time lookup.

Approach 3: Array Mapping Optimization (O(n) time, O(1) space)

Instead of a hash map, use a fixed array of size 26 where index = char - 'a'. Populate the array with keyboard positions during a single pass. When processing the word, retrieve each character’s keyboard index directly from the array and accumulate the distance. This avoids hash overhead and keeps memory constant. The technique is a lightweight simulation pattern often used in string and keyboard‑layout problems.

Recommended for interviews: Use the index mapping approach with a hash map or array. It runs in O(n) time and demonstrates good preprocessing habits. The brute simulation shows you understand the problem mechanics, but interviewers expect you to remove the repeated keyboard scans and achieve constant‑time lookups using hashing or indexing.

Solution

We define a hash table pos to store the position of each character on the keyboard. For each character in string s, we calculate the distance from the previous character to the current character and accumulate it to the answer. Finally, we return the answer.

The time complexity is O(n), where n is the length of string s. The space complexity is O(|\Sigma|), where \Sigma is the character set, which here is 26 lowercase English letters.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Linear Search SimulationO(26 * n)O(1)Quick brute-force idea when constraints are small and preprocessing is skipped
Hash Table Index MappingO(n)O(26)General solution with fast lookups; common interview approach
Array Index MappingO(n)O(1)Most efficient implementation when characters are limited to lowercase letters

Video Solution

Total Distance to Type a String Using One Finger • Owen Wu • 440 views views

Frequently Asked Questions

Is Total Distance to Type a String Using One Finger easy or hard?
The problem is typically classified as Medium because it requires recognizing the preprocessing optimization. The brute approach works but repeatedly scans the keyboard. Efficient solutions use a hash map or array to reduce lookups to O(1) and achieve an overall O(n) runtime.
Total Distance to Type a String Using One Finger Python/Java solution
The standard implementation first builds a dictionary (Python) or HashMap/array (Java) mapping each keyboard character to its position. Then iterate through the word, compute absolute differences between consecutive positions, and sum them. This approach runs in O(n) time and uses O(1) additional space.
How to solve Total Distance to Type a String Using One Finger in O(n)?
First build a map or array that stores the index of every character in the keyboard layout. Then iterate through the word and compute the distance between the current character and the previous one using abs(position[a] - position[b]). Accumulate these values to get the total distance. Because each lookup is O(1), the overall complexity is O(n).
What is the best approach for Total Distance to Type a String Using One Finger?
The best approach builds a mapping from each keyboard character to its index, then simulates typing the word. This allows constant‑time lookup of positions and computes the distance between consecutive characters using absolute difference. The total runtime is O(n) where n is the word length, with O(26) extra space for the mapping.
Is Total Distance to Type a String Using One Finger asked at Google/Amazon/Meta?
Problems involving keyboard layouts, string indexing, and distance simulation commonly appear in interviews at companies like Google, Amazon, and Meta. While this exact question may vary, the pattern of preprocessing indices and computing movement cost is frequently tested in string and simulation questions.
What data structure is used in Total Distance to Type a String Using One Finger?
The main data structure is a hash table or a fixed array used to store the keyboard index of each character. This enables constant‑time access when calculating distances between characters. The rest of the solution is a straightforward simulation over the input string.
What is the time complexity of Total Distance to Type a String Using One Finger?
The optimal solution runs in O(n) time where n is the length of the word. A preprocessing step maps each character in the keyboard to its index in O(26) time. Each character in the word is then processed once with constant‑time lookups, so the total runtime remains linear.

Ready to solve this problem?

Practice Total Distance to Type a String Using One Finger with our built-in code editor and test cases.

Practice on FleetCode
Previous

Single-Row Keyboard