Skip to content

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

Solutions

Solution 1: Simulation

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
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;
}

Comments