3846. Total Distance to Type a String Using One Finger 🔒

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|.

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 <= 10⁴
s consists of lowercase English letters only.

Solutions

Solution 1: Simulation

Thinking

One finger starts at \(\texttt{a}\) and types \(s\) in order, paying Manhattan distance on the keyboard grid. \(|s| \le 10^4\) and the layout is fixed.

The distance between two successive keys depends only on those two coordinates.

Precompute the three-row positions, then accumulate adjacent Manhattan distances from an implicit start at \(\texttt{a}\).

One scan is the total travel.

We define a hash table \(\textit{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.

Python3JavaC++GoTypeScript

pos = {}
keys = ['qwertyuiop', 'asdfghjkl', 'zxcvbnm']
for (i, row) in enumerate(keys):
    for (j, key) in enumerate(row):
        pos[key] = (i, j)


class Solution:
    def totalDistance(self, s: str) -> int:
        pre = 'a'
        ans = 0
        for cur in s:
            x1, y1 = pos[pre]
            x2, y2 = pos[cur]
            dist = abs(x1 - x2) + abs(y1 - y2)
            ans += dist
            pre = cur
        return ans

class Solution {
    private static final Map<Character, int[]> pos = new HashMap<>();

    static {
        String[] keys = {"qwertyuiop", "asdfghjkl", "zxcvbnm"};
        for (int i = 0; i < keys.length; i++) {
            for (int j = 0; j < keys[i].length(); j++) {
                pos.put(keys[i].charAt(j), new int[] {i, j});
            }
        }
    }

    public int totalDistance(String s) {
        char pre = 'a';
        int ans = 0;

        for (char cur : s.toCharArray()) {
            int[] p1 = pos.get(pre);
            int[] p2 = pos.get(cur);
            ans += Math.abs(p1[0] - p2[0]) + Math.abs(p1[1] - p2[1]);
            pre = cur;
        }

        return ans;
    }
}

class Solution {
public:
    int totalDistance(string s) {
        static unordered_map<char, pair<int, int>> pos = [] {
            unordered_map<char, pair<int, int>> m;
            vector<string> keys = {"qwertyuiop", "asdfghjkl", "zxcvbnm"};
            for (int i = 0; i < keys.size(); ++i) {
                for (int j = 0; j < keys[i].size(); ++j) {
                    m[keys[i][j]] = {i, j};
                }
            }
            return m;
        }();

        char pre = 'a';
        int ans = 0;

        for (char cur : s) {
            auto [x1, y1] = pos[pre];
            auto [x2, y2] = pos[cur];
            ans += abs(x1 - x2) + abs(y1 - y2);
            pre = cur;
        }

        return ans;
    }
};

var pos map[byte][2]int

func init() {
    pos = make(map[byte][2]int)
    keys := []string{"qwertyuiop", "asdfghjkl", "zxcvbnm"}
    for i, row := range keys {
        for j := 0; j < len(row); j++ {
            pos[row[j]] = [2]int{i, j}
        }
    }
}

func totalDistance(s string) int {
    pre := byte('a')
    ans := 0

    for i := 0; i < len(s); i++ {
        cur := s[i]
        p1 := pos[pre]
        p2 := pos[cur]
        ans += abs(p1[0]-p2[0]) + abs(p1[1]-p2[1])
        pre = cur
    }

    return ans
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

const pos: Record<string, [number, number]> = {};

const keys = ['qwertyuiop', 'asdfghjkl', 'zxcvbnm'];
keys.forEach((row, i) => {
    [...row].forEach((key, j) => {
        pos[key] = [i, j];
    });
});

function totalDistance(s: string): number {
    let pre = 'a';
    let ans = 0;

    for (const cur of s) {
        const [x1, y1] = pos[pre];
        const [x2, y2] = pos[cur];
        ans += Math.abs(x1 - x2) + Math.abs(y1 - y2);
        pre = cur;
    }

    return ans;
}

3846. Total Distance to Type a String Using One Finger 🔒

Description

Solutions

Solution 1: Simulation

Comments