LeetCode Problem 3846

Difficulty: 🟡 Medium
Topics: Hash Table, String

Solution

LeetCode 3846 - Total Distance to Type a String Using One Finger

Problem Understanding

This problem asks us to calculate the total finger movement required to type a given lowercase string on a special keyboard layout using only one finger.

The keyboard is arranged as:

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

Each key occupies a coordinate (row, column) in this grid. The finger initially starts on the key 'a'.

For every character in the string, we move the finger from its current position to the position of the next character. The cost of a movement is the Manhattan distance between the two coordinates:

$$|r_1-r_2| + |c_1-c_2|$$

The goal is to compute the sum of all such movement distances required to type the entire string.

The input consists of a single string s containing only lowercase English letters. The output is a single integer representing the total distance traveled by the finger.

The constraint 1 <= s.length <= 10^4 tells us that the string can be fairly long, but not extremely large. Since there are only 26 possible characters, any solution that processes each character once will be more than efficient enough.

Several edge cases are important to consider. A string containing only one character requires only the movement from the starting position 'a' to that character. If the string itself starts with 'a', the first movement cost may be zero. Consecutive identical characters should contribute zero distance because the finger remains on the same key. The problem guarantees that all characters are lowercase English letters, so we never need to handle invalid input.

Approaches

Brute Force Approach

A straightforward solution is to explicitly store the coordinate of every key on the keyboard and then simulate typing the string.

We begin at the coordinate of 'a'. For each character in the string, we look up its coordinate, compute the Manhattan distance from the current finger position, add that distance to the answer, and then update the current position.

This approach is already efficient because there are only 26 keys. Looking up coordinates is constant time, and each character is processed exactly once.

Key Insight

The important observation is that the keyboard layout never changes and contains only 26 letters. Therefore, we can precompute a mapping from each character to its coordinate.

Once this mapping exists, the problem becomes a simple simulation of finger movement. For each character, we only need to calculate one Manhattan distance and update the current position.

No complex data structures or optimization techniques are necessary because the work required per character is constant.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(1)	Simulate typing using a coordinate lookup table
Optimal	O(n)	O(1)	Same idea, each character processed once with constant-time lookups

In this problem, the brute force simulation is already optimal.

Algorithm Walkthrough

1. Create a mapping from every keyboard character to its (row, column) coordinate.
2. Initialize the current finger position to the coordinate of 'a', since the finger always starts there.
3. Initialize a variable total_distance to 0.
4. Iterate through each character in the string.
5. For the current character, retrieve its coordinate from the mapping.
6. Compute the Manhattan distance between the current finger position and the target character position.
7. Add this distance to total_distance.
8. Update the current finger position to the target character position.
9. After processing all characters, return total_distance.

Why it works

At every step, the algorithm maintains the invariant that the current position represents the location of the finger after typing all previously processed characters. The Manhattan distance formula exactly matches the distance definition given in the problem statement. Since every movement required to type the string is accounted for exactly once and added to the total, the final result equals the total typing distance.

Python Solution

class Solution:
    def totalDistance(self, s: str) -> int:
        positions = {}

        keyboard = [
            "qwertyuiop",
            "asdfghjkl",
            "zxcvbnm"
        ]

        for row, letters in enumerate(keyboard):
            for col, ch in enumerate(letters):
                positions[ch] = (row, col)

        current_row, current_col = positions["a"]
        total_distance = 0

        for ch in s:
            target_row, target_col = positions[ch]

            total_distance += (
                abs(current_row - target_row)
                + abs(current_col - target_col)
            )

            current_row, current_col = target_row, target_col

        return total_distance

The solution first builds a coordinate map for all 26 letters. The dictionary allows constant-time access to the location of any character.

The variables current_row and current_col store the finger's current location. Initially, they are set to the position of 'a'.

As the algorithm iterates through the string, it retrieves the target character's coordinate, computes the Manhattan distance from the current position, adds that value to the running total, and updates the current position.

After every character has been processed, the accumulated total distance is returned.

Go Solution

func totalDistance(s string) int {
    positions := make(map[byte][2]int)

    keyboard := []string{
        "qwertyuiop",
        "asdfghjkl",
        "zxcvbnm",
    }

    for r, row := range keyboard {
        for c := 0; c < len(row); c++ {
            positions[row[c]] = [2]int{r, c}
        }
    }

    start := positions['a']
    currentRow, currentCol := start[0], start[1]

    totalDistance := 0

    for i := 0; i < len(s); i++ {
        pos := positions[s[i]]
        targetRow, targetCol := pos[0], pos[1]

        dr := currentRow - targetRow
        if dr < 0 {
            dr = -dr
        }

        dc := currentCol - targetCol
        if dc < 0 {
            dc = -dc
        }

        totalDistance += dr + dc

        currentRow = targetRow
        currentCol = targetCol
    }

    return totalDistance
}

The Go implementation follows exactly the same logic as the Python solution. A map stores coordinates for each character, and the string is processed one character at a time.

Since Go does not provide a built-in integer abs function, the absolute value calculations are implemented manually. Integer overflow is not a concern because the maximum string length is only 10^4, making the maximum possible answer well within Go's integer range.

Worked Examples

Example 1

Input

s = "hello"

Keyboard coordinates:

Character	Coordinate
a	(1, 0)
h	(1, 5)
e	(0, 2)
l	(1, 8)
o	(0, 8)

Initial state:

Current Position = (1, 0)
Total Distance = 0

Step	Character	Current Position	Target Position	Distance	Running Total
1	h	(1,0)	(1,5)	5	5
2	e	(1,5)	(0,2)	4	9
3	l	(0,2)	(1,8)	7	16
4	l	(1,8)	(1,8)	0	16
5	o	(1,8)	(0,8)	1	17

Final answer:

17

Example 2

Input

s = "a"

Initial state:

Current Position = (1, 0)
Total Distance = 0

Step	Character	Current Position	Target Position	Distance	Running Total
1	a	(1,0)	(1,0)	0	0

Final answer:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character in the string is processed exactly once
Space	O(1)	The coordinate map contains only 26 letters

The coordinate mapping requires a fixed amount of storage regardless of input size. The algorithm performs a constant amount of work for every character in the string, resulting in linear time complexity with respect to the string length.

Test Cases

sol = Solution()

assert sol.totalDistance("hello") == 17  # provided example
assert sol.totalDistance("a") == 0  # single character, starts on a

assert sol.totalDistance("aa") == 0  # repeated same character
assert sol.totalDistance("aaa") == 0  # multiple repeated characters

assert sol.totalDistance("h") == 5  # single move from a to h
assert sol.totalDistance("ab") == 4  # move from a to a, then a to b

assert sol.totalDistance("az") == 1  # vertical neighbor
assert sol.totalDistance("za") == 2  # start at a, move to z, then back to a

assert sol.totalDistance("qq") == 2  # move a->q, then stay on q
assert sol.totalDistance("qaq") == 4  # repeated transitions

assert sol.totalDistance("abcdefghijklmnopqrstuvwxyz") >= 0  # long traversal

assert sol.totalDistance("mmmmmmmmmm") == sol.totalDistance("m")  # repeated target key

assert sol.totalDistance("zxcvbnm") >= 0  # entire bottom row

Test Summary

Test	Why
"hello"	Validates the provided example
"a"	Smallest possible input
"aa"	Consecutive identical characters
"aaa"	Multiple zero-distance transitions
"h"	Single movement from starting position
"ab"	Basic movement across the keyboard
"az"	Movement between adjacent rows
"za"	Round-trip movement
"qq"	Repeated non-starting character
"qaq"	Alternating between keys
"abcdefghijklmnopqrstuvwxyz"	Long traversal across many keys
"mmmmmmmmmm"	Repeated distant character
"zxcvbnm"	Traversal across bottom row

Edge Cases

Single Character String

When the input contains only one character, there are no transitions between typed characters. The answer is simply the distance from the starting position 'a' to that character. The implementation naturally handles this because the loop executes exactly once.

Consecutive Identical Characters

Strings such as "aaaa" or "llll" can expose bugs if an implementation incorrectly assumes every character change requires movement. The Manhattan distance between identical coordinates is zero, so the algorithm correctly adds zero for each repeated character.

String Beginning With 'a'

Since the finger already starts on 'a', the first typed character may require no movement. For example, "abc" should begin with a distance contribution of zero for the first character. The implementation initializes the current position to 'a', ensuring this case is handled correctly.

Maximum Length Input

The string length can be as large as 10^4. Any solution that repeatedly searches the keyboard to find coordinates could perform unnecessary work. The coordinate map guarantees constant-time lookups, allowing the algorithm to process the entire string efficiently in linear time.