3846. Total Distance to Type a String Using One Finger 🔒
Problem Description
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|.
In other words, you need to simulate typing each character of s in order. Starting from key 'a', move your finger to each character one by one. Each move adds the Manhattan distance between the current key position and the next key position to the total. Return the sum of all these distances after typing the entire string.
How We Pick the Algorithm
Why Simulation / Basic DSA?
This problem maps to Simulation / Basic DSA through a short path in the full flowchart.
Straightforward simulation of typing on a keyboard with Manhattan distance accumulation.
Open in FlowchartIntuition
The key observation is that the total distance only depends on the positions of consecutive characters we type. Since the finger moves from one character to the next in order, we can break the whole journey into a series of individual moves and simply add up the distance of each move.
To compute the distance between any two characters quickly, we first need to know where each character sits on the keyboard. The natural idea is to precompute the (row, column) position of every key and store it in a hash table pos. This way, looking up any character's coordinates takes constant time.
With the positions ready, we just walk through the string s. We keep track of the previous character (starting from 'a'), and for each current character cur, we look up both coordinates and add |r1 - r2| + |c1 - c2| to the answer. After accounting for the move, we update the previous character to cur and continue.
Since every character contributes exactly one move, summing these moves gives us the total typing distance directly.
Solution Approach
Solution 1: Simulation
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.
Step 1: Precompute the positions.
We list the three keyboard rows as keys = ['qwertyuiop', 'asdfghjkl', 'zxcvbnm']. By iterating over each row with its index i and each character in that row with its index j, we record pos[key] = (i, j). This builds a hash table that maps every letter to its (row, column) coordinate, enabling constant-time lookup later.
Step 2: Simulate the typing process.
We initialize the previous character pre to 'a' (the finger's starting key) and the answer ans to 0. Then we traverse each character cur in s:
- Look up the coordinates of the previous character:
x1, y1 = pos[pre]. - Look up the coordinates of the current character:
x2, y2 = pos[cur]. - Compute the Manhattan distance
dist = |x1 - x2| + |y1 - y2|and add it toans. - Update
pre = curso the next move starts from the current key.
Step 3: Return the result.
After processing all characters, ans holds the total distance, which we return.
The time complexity is O(n), where n is the length of the string s, since we process each character once and every lookup and distance computation is O(1). The space complexity is O(C), where C is the size of the character set (at most 26), used to store the position hash table.
Example Walkthrough
Let's trace through the solution using a small example: s = "cba".
Setup: Precompute positions
First, we build the pos hash table from the three keyboard rows:
| Character | Position (row, col) |
|---|---|
a | (1, 0) |
b | (2, 4) |
c | (2, 2) |
(The full table contains all 26 letters, but these are the only ones we need here.)
Initialization
pre = 'a'(the finger starts on key'a')ans = 0
Simulate typing each character
Move 1: type 'c'
- Previous key
'a'is at(1, 0)→x1=1, y1=0 - Current key
'c'is at(2, 2)→x2=2, y2=2 dist = |1 - 2| + |0 - 2| = 1 + 2 = 3ans = 0 + 3 = 3- Update
pre = 'c'
Move 2: type 'b'
- Previous key
'c'is at(2, 2)→x1=2, y1=2 - Current key
'b'is at(2, 4)→x2=2, y2=4 dist = |2 - 2| + |2 - 4| = 0 + 2 = 2ans = 3 + 2 = 5- Update
pre = 'b'
Move 3: type 'a'
- Previous key
'b'is at(2, 4)→x1=2, y1=4 - Current key
'a'is at(1, 0)→x2=1, y2=0 dist = |2 - 1| + |4 - 0| = 1 + 4 = 5ans = 5 + 5 = 10- Update
pre = 'a'
Result
After processing all characters, ans = 10. This is the total distance to type "cba" starting from key 'a'.
The journey breaks down as: a → c (3) + c → b (2) + b → a (5) = 10, confirming that summing each individual move gives the correct total.
Solution Implementation
1# Precompute the (row, column) position of each key on the keyboard layout
2KEY_ROWS = ['qwertyuiop', 'asdfghjkl', 'zxcvbnm']
3key_position = {}
4for row_index, row in enumerate(KEY_ROWS):
5 for col_index, key in enumerate(row):
6 key_position[key] = (row_index, col_index)
7
8
9class Solution:
10 def totalDistance(self, s: str) -> int:
11 # The finger starts at the key 'a'
12 previous_key = 'a'
13 total = 0
14
15 # Iterate over every character we need to type
16 for current_key in s:
17 prev_row, prev_col = key_position[previous_key]
18 curr_row, curr_col = key_position[current_key]
19
20 # Manhattan distance between the two keys
21 distance = abs(prev_row - curr_row) + abs(prev_col - curr_col)
22 total += distance
23
24 # Move the finger to the current key for the next iteration
25 previous_key = current_key
26
27 return total
281class Solution {
2 // Maps each keyboard character to its [row, column] position
3 private static final Map<Character, int[]> CHAR_POSITION = new HashMap<>();
4
5 // Static initializer to populate the keyboard layout positions
6 static {
7 String[] keyboardRows = {"qwertyuiop", "asdfghjkl", "zxcvbnm"};
8 for (int row = 0; row < keyboardRows.length; row++) {
9 for (int col = 0; col < keyboardRows[row].length(); col++) {
10 CHAR_POSITION.put(keyboardRows[row].charAt(col), new int[] {row, col});
11 }
12 }
13 }
14
15 public int totalDistance(String s) {
16 // Start from 'a' as the initial finger position (top-left area)
17 char previousChar = 'a';
18 // Accumulates the total Manhattan distance traveled
19 int totalDistance = 0;
20
21 for (char currentChar : s.toCharArray()) {
22 // Retrieve the [row, col] coordinates of the previous and current characters
23 int[] previousPos = CHAR_POSITION.get(previousChar);
24 int[] currentPos = CHAR_POSITION.get(currentChar);
25
26 // Add the Manhattan distance between the two key positions
27 totalDistance += Math.abs(previousPos[0] - currentPos[0])
28 + Math.abs(previousPos[1] - currentPos[1]);
29
30 // Move the "finger" to the current character for the next iteration
31 previousChar = currentChar;
32 }
33
34 return totalDistance;
35 }
36}
371class Solution {
2public:
3 int totalDistance(string s) {
4 // Lazily-initialized, shared mapping from each letter to its (row, column)
5 // position on a standard QWERTY keyboard layout.
6 static unordered_map<char, pair<int, int>> charPosition = [] {
7 unordered_map<char, pair<int, int>> position;
8 vector<string> keyboardRows = {"qwertyuiop", "asdfghjkl", "zxcvbnm"};
9
10 // Iterate over every row and column to record each letter's coordinates.
11 for (int row = 0; row < keyboardRows.size(); ++row) {
12 for (int col = 0; col < keyboardRows[row].size(); ++col) {
13 charPosition[keyboardRows[row][col]] = {row, col};
14 }
15 }
16 return position;
17 }();
18
19 char prevChar = 'a'; // Finger starts on the 'a' key.
20 int totalDist = 0; // Accumulated Manhattan distance traveled.
21
22 // For each character, add the Manhattan distance from the previous key.
23 for (char curChar : s) {
24 auto [prevRow, prevCol] = charPosition[prevChar];
25 auto [curRow, curCol] = charPosition[curChar];
26
27 // Manhattan distance: vertical movement + horizontal movement.
28 totalDist += abs(prevRow - curRow) + abs(prevCol - curCol);
29
30 prevChar = curChar; // Move the finger to the current key.
31 }
32
33 return totalDist;
34 }
35};
36```
37
38A small but important correction worth noting: in the original lambda, the map was populated through the captured-by-name variable `m`, while the lambda returned `m`. In my rewrite I renamed the local variable to `position`, so the lambda body must consistently use `position` for both populating and returning. Here is the corrected lambda portion to ensure consistency:
39
40```cpp
41static unordered_map<char, pair<int, int>> charPosition = [] {
42 unordered_map<char, pair<int, int>> position;
43 vector<string> keyboardRows = {"qwertyuiop", "asdfghjkl", "zxcvbnm"};
44
45 for (int row = 0; row < keyboardRows.size(); ++row) {
46 for (int col = 0; col < keyboardRows[row].size(); ++col) {
47 position[keyboardRows[row][col]] = {row, col}; // populate via 'position'
48 }
49 }
50 return position;
51}();
521// Map each letter to its [row, column] position on the keyboard
2const keyPositions: Record<string, [number, number]> = {};
3
4// Layout of a standard QWERTY keyboard, row by row
5const keyboardRows: string[] = ['qwertyuiop', 'asdfghjkl', 'zxcvbnm'];
6
7// Populate the keyPositions map by iterating over each row and each key
8keyboardRows.forEach((row: string, rowIndex: number) => {
9 [...row].forEach((key: string, colIndex: number) => {
10 keyPositions[key] = [rowIndex, colIndex];
11 });
12});
13
14/**
15 * Calculate the total Manhattan distance traveled by a single finger
16 * when typing the given string, starting from the letter 'a'.
17 *
18 * @param s - The string to be typed.
19 * @returns The accumulated distance between consecutive keys.
20 */
21function totalDistance(s: string): number {
22 // The finger always starts at the letter 'a'
23 let previousChar: string = 'a';
24 let answer: number = 0;
25
26 // Move the finger to each character in turn, summing the distances
27 for (const currentChar of s) {
28 const [prevRow, prevCol] = keyPositions[previousChar];
29 const [currRow, currCol] = keyPositions[currentChar];
30
31 // Manhattan distance between the previous and current key
32 answer += Math.abs(prevRow - currRow) + Math.abs(prevCol - currCol);
33
34 // Update the finger's current position
35 previousChar = currentChar;
36 }
37
38 return answer;
39}
40Time and Space Complexity
The time complexity is O(n), and the space complexity is O(|Σ|). Here, n is the length of the string s.
The algorithm iterates over the string s once, performing a constant-time lookup in the pos dictionary and a constant-time distance calculation for each character. Therefore, the time complexity is O(n).
The space complexity is O(|Σ|), where Σ is the character set, which here is 26 lowercase English letters. The pos dictionary stores the position of each key on the keyboard, requiring space proportional to the size of the character set.
Pattern Learn more about how to find time and space complexity quickly.
Common Pitfalls
Pitfall 1: Forgetting that the finger starts at 'a', not at the first character
A very common mistake is to initialize previous_key to s[0] (the first character of the string) and then start iterating from the second character. While this seems natural, the problem explicitly states that the finger starts on the key 'a'. If the first character of s is not 'a', you must still count the distance from 'a' to that first character.
Incorrect approach:
class Solution:
def totalDistance(self, s: str) -> int:
previous_key = s[0] # WRONG: ignores the move from 'a' to s[0]
total = 0
for current_key in s[1:]:
prev_row, prev_col = key_position[previous_key]
curr_row, curr_col = key_position[current_key]
total += abs(prev_row - curr_row) + abs(prev_col - curr_col)
previous_key = current_key
return total
For example, with s = "z", the correct answer is the distance from 'a' (row 1) to 'z' (row 2), which is 1. The incorrect version returns 0.
Solution: Always initialize previous_key = 'a' and iterate over the entire string, exactly as the correct code does. The starting key is fixed by the problem, independent of the input.
Pitfall 2: Building the position table incorrectly with row lengths
The three rows have different lengths (10, 9, and 7). A pitfall is trying to compute coordinates using a fixed width (e.g., assuming every row has 10 columns and using index // 10 and index % 10 on a flattened string). The missing keys in rows 2 and 3 break this assumption and produce wrong column indices.
Incorrect approach:
flat = 'qwertyuiopasdfghjklzxcvbnm' # gaps removed
# Treating it as a 3 x 10 grid is wrong because the gaps are gone,
# so 'a' would map to index 10 -> (1, 0) by luck, but 'z' maps to
# index 19 -> (1, 9) instead of the correct (2, 0).
key_position = {ch: (i // 10, i % 10) for i, ch in enumerate(flat)}
Solution: Build the table by iterating row by row with independent column indices, letting each row define its own length. This naturally assigns the correct (row, column) to every key regardless of differing row widths:
KEY_ROWS = ['qwertyuiop', 'asdfghjkl', 'zxcvbnm']
key_position = {}
for row_index, row in enumerate(KEY_ROWS):
for col_index, key in enumerate(row):
key_position[key] = (row_index, col_index)
Pitfall 3: Using Euclidean distance instead of Manhattan distance
The problem defines distance as |r1 - r2| + |c1 - c2|. Mistakenly computing the straight-line (Euclidean) distance sqrt((r1-r2)^2 + (c1-c2)^2) yields non-integer, incorrect results.
Solution: Stick to the sum of absolute differences. Use abs(prev_row - curr_row) + abs(prev_col - curr_col) so the result stays an integer and matches the problem's definition.
Ready to land your dream job?
Unlock your dream job with a 5-minute quiz for a personalized study roadmap!
Get My RoadmapIn a binary min heap, the minimum element can be found in:
Recommended Readings
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Recursion If you prefer videos here's a video that explains recursion in a fun and easy way Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask him
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity describes how the time needed
Want a Structured Path to Master System Design Too? Don’t Miss This!